graph - How to construct a graph for triangular strips in linear time even for worst case?

Question

In Graph, there is a triangular strip problem. Basically, we have a set of adjacent triangles and we want to consider each triangle as a new vertex and there will be an edge between two new vertices if the two triangles behind them have an edge in common.

My question here is about reading each triangle and construct the new strip graph for them.

For example, we have these triangles (A, B and C):

A - 0, 1, 3

B - 1, 2, 3

C - 2, 3, 4

so A and B have a common edge and so do B and C. the new strip go from A to B and then to C.

Ok. I think one of the key things here is that each time when you read a new triangle, we want to know which triangles have common edges with the new one.

A stupid way is that we just scan all old triangles and compare their three vertices with the new one's vertices, and if two vertices match, then there is a adjacency.

A better way (described in The Algorithm Design Manual) is that each time when we create a list for each triangle vertex. That list contains all triangles that pass through the vertex. for example, for the triangles above, vertex 0 has the list of {A}, vertex 1 has the list of {A, B}, etc. So when a new triangle comes, we just need to check 3 vertices and try to find which old triangles having two common vertices with the new one.

Here comes some questions:

1. Is the better way linear? How to define the "linear" for this kind of reading and constructing graph? For example, in the better way, a new triangle need to go through 3 lists of old triangles. Is this linear enough? I thought it is linear because at most it just read all old triangles. But if my thought is true, then the stupid way is also linear, right? so I guess I may be wrong, but very confused.

2. Will there be a even better way? This is asked by Algorithm Design Manual as an excise and that excise asks for a pure linear algorithm even in worst case.

My solution for a even better way is that instead of build a list for each vertex, I build a list for each edge. A vertex can have many triangles passing through, but with an edge, there will be at most two triangles passing assuming that all triangles' edges are not crossing each other and at most merge (in common).

Then each edge has a list of at most two items. and for a newly coming triangle, it need to check at most 3 edges. I think it is better than the better way above.

Am I right? or Is my better better way a pure best linear solution?

Answer 1

Is the better way linear?

No, it is not. As you say, yes there will be three lists to examine which is a much more smaller space than the whole old triangles as the Stupid Way does, but the length of these lists are growing, again linearly as the number of triangles examined grows. In the worst case, the better way has the same complexity as the stupid way which is polynomial (the case where all triangles share a vertex)

A - 0, 1, 2

B - 0, 2, 3

C - 0, 3, 4

D - 0, 4, 5

...

About your solution to this problem, you are right, yours is a linear one assuming fetching an edge from the previously created edges is done in constant time (a hashtable like structure is required, not a list).

Moreover, you can improve yours as just remembering the edges that have been added to the list (hashtable?) once, and removing those that are encountered twice (since it is assumed that an edge can only be shared between two triangles)