在Graph中，有一个triangular strip问题。基本上，我们有一组相邻的三角形，我们想将每个三角形视为一个新顶点，如果两个新顶点后面的两个三角形有一条公共(public)边，则两个新顶点之间将有一条边。
我这里的问题是关于读取每个三角形并为它们构建新的带状图。
例如，我们有这些三角形(A、B 和 C):
A - 0, 1, 3
B - 1, 2, 3
C - 2, 3, 4
所以 A 和 B 有公共(public)边，B 和 C 也有公共(public)边。新 strip 从 A 到 B，然后到 C。
好的。我认为这里的关键之一是每次当你读取一个新三角形时，我们想知道哪些三角形与新三角形有公共(public)边。
一个愚蠢的方法是我们只是扫描所有旧三角形并将它们的三个顶点与新三角形的顶点进行比较，如果两个顶点匹配，则存在邻接。
更好的方法(在 Algorithm Design Manual 中描述)是每次我们为每个三角形顶点创建一个列表。该列表包含所有通过顶点的三角形。例如，对于上面的三角形，顶点 0 有 {A} 的列表，顶点 1 有 {A，B} 的列表，等等。所以当一个新的三角形出现时，我们只需要检查 3 个顶点并尝试找到哪些旧三角形与新三角形有两个公共(public)顶点。
这里有一些问题:
更好的方法是线性的吗？这种读图建图的“线性”如何定义？例如，更好的方法是，一个新三角形需要遍历 3 个旧三角形列表。这够线性吗？我认为它是线性的，因为它最多只是读取所有旧三角形。但是如果我的想法是真的，那么笨办法也是线性的，对吧？所以我想我可能是错的，但很困惑。
还有更好的方法吗？这是由 Algorithm Design Manual 询问的作为消费税，即使在最坏的情况下，消费税也需要纯线性算法。
我的一个更好的解决方案是，我不是为每个顶点构建一个列表，而是为每个边缘构建一个列表。一个顶点可以有许多三角形通过，但如果有一条边，则最多有两个三角形通过，前提是所有三角形的边不相互交叉并且最多合并(共同)。
那么每条边都有一个最多包含两项的列表。对于新出现的三角形，它最多需要检查 3 条边。我认为它比上面的更好的方法要好。
我说得对吗？还是我更好的方法是纯最佳线性解决方案？
最佳答案
Is the better way linear?
不，不是。正如你所说，是的，将有三个列表来检查哪个空间比整个旧三角形小得多，就像 Stupid Way 所做的那样，但是这些列表的长度正在增长，再次线性增长检查的三角形数量增加。在最坏的情况下，更好的方法与愚蠢的方法具有相同的复杂性，即多项式(所有三角形共享一个顶点的情况)
A - 0, 1, 2
B - 0, 2, 3
C - 0, 3, 4
D - 0, 4, 5
...
关于您对这个问题的解决方案，您是对的，您的解决方案是线性的，假设从先前创建的边中获取边是在恒定时间内完成的(需要类似哈希表的结构，而不是列表)。
此外，您可以改进您的方法，只需记住已添加到列表(哈希表？)中的边一次，并删除遇到两次的边(因为假定边只能在两个三角形之间共享)
关于algorithm - graph - 即使在最坏的情况下，如何在线性时间内构建三角形带的图形？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10122552/