在图中，存在三角形条带问题。基本上，我们有一组相邻的三角形，我们希望将每个三角形视为一个新顶点，如果它们后面的两个三角形有一个共同的边，则两个新顶点之间将有一个边。
我在这里的问题是关于阅读每个三角形并为它们构建新的带状图。
例如，我们有这些三角形（A、B 和 C）：
A - 0， 1， 3
B - 1， 2， 3
C - 2， 3， 4
所以 A 和 B 有一个共同的边，B 和 C 也是如此。
还行。我认为这里的关键之一是，每次阅读新三角形时，我们都想知道哪些三角形与新三角形有共同的边。
一个愚蠢的方法是，我们只是扫描所有旧的三角形，并将它们的三个顶点与新三角形的顶点进行比较，如果两个顶点匹配，则存在邻接关系。
更好的方法（在算法设计手册中描述）是每次我们为每个三角形顶点创建一个列表时。该列表包含穿过顶点的所有三角形。例如，对于上面的三角形，顶点 0 有 {A} 的列表，顶点 1 有 {A、B} 的列表，依此类推。因此，当一个新三角形出现时，我们只需要检查 3 个顶点，并尝试找到哪些旧三角形与新三角形具有两个共同顶点。
这里有一些问题：
-
更好的方法是线性的吗？如何定义这种读取和构造图的"线性"？例如，以更好的方式，一个新三角形需要经过 3 个旧三角形列表。这足够线性吗？我认为它是线性的，因为它最多只读取所有旧的三角形。但是如果我的想法是正确的，那么愚蠢的方式也是线性的，对吧？所以我想我可能是错的，但非常困惑。
-
会有更好的方法吗？这是算法设计手册要求作为消费税的，即使在最坏的情况下，消费税也要求纯线性算法。
我的解决方案是，我不是为每个顶点构建一个列表，而是为每个边构建一个列表。一个顶点可以有许多三角形通过，但是对于一条边，假设所有三角形的边没有相互交叉并且最多合并（共同），则最多有两个三角形通过。
然后，每条边都有一个最多包含两个项目的列表。 对于新来的三角形，它最多需要检查 3 条边。我认为它比上面的更好方法更好。
我说的对吗？或者我更好的更好方法是纯粹的最佳线性解决方案吗？
更好的方法是线性的吗？
不，不是。正如你所说，是的，将有三个列表需要检查，哪个列表比整个旧三角形要小得多，就像愚蠢的方式一样，但是这些列表的长度正在增长，随着检查的三角形数量的增加，再次呈线性增长。在最坏的情况下，更好的方法与多项式的愚蠢方法具有相同的复杂性（所有三角形共享一个顶点的情况）
A - 0， 1， 2
B - 0， 2， 3
C - 0， 3， 4
D - 0， 4， 5
。
关于你对这个问题的解决方案，你是对的，你的是一个线性的，假设从先前创建的边中获取边缘是在恒定时间内完成的（需要一个类似哈希表的结构，而不是列表）。
此外，你可以改进你的，只记住一次添加到列表（哈希表？）的边，并删除那些遇到两次的边（因为假设一条边只能在两个三角形之间共享）