How to add a diagonal to a doubly-connected edge list in constant time?

Question

I'm working through the polygon triangulation algorithm in Computational Geometry: Algorithms and Applications, 3rd edition, by Mark de Berg and others. The data structure used to represent the polygon is called a "doubly-connected edge list". As the book describes, "[it] contains a record for each face, edge, and vertex". Each edge is actually stored as two "half edges", representing each side of the edge. This makes it easier to walk the half edges around a face. The half edge records look like:

// Pseudocode. No particular language. The properties need to be pointers/references of some kind.
struct HalfEdge {
   Vertex   origin;
   HalfEdge twin;
   Face     incidentFace;
   HalfEdge next;
   HalfEdge previous;
}

Now imagine I'm processing this polygon, with one face (so far) called Face1. I need to add a diagonal at the dotted line. This will create a new face (Face2). It seems like I need to walk all those HalfEdges that now surround Face2 and set their incidentFace property to point to Face2.

But the book says:

The diagonals computed for the split and merge vertices are added to the doubly-connected edge list. To access the doubly-connected edge list we use cross-pointers between the edges in the status structure and the corresponding edges in the doubly-connected edge list. Adding a diagonal can then be done in constant time with some simple pointer manipulations.

I don't see any further explanation. I'm not sure what a "cross pointer" means here. The "status structure" refers to a binary search tree of edges that is used to easily find the edge to the left of a given vertex, as the polygon is processed from top to bottom.

Can anyone explain this further? How are they able to update all the edges in constant time?

Do you read the book by Mark de Berg and others from 2008? I can't find phrase "Adding a diagonal can then be done in constant time" in this book. Chapter number and page number would be helpful — HEKTO, Jul 31 '22 at 17:42
Yes that's the book. I just edited the question to add his name, to better identify the book. It's chapter 3, section 3.2. It appears in my edition on page 53 right before the "MakeMonotone" algorithm pseudocode. — Rob N, Aug 01 '22 at 20:04

score 1 · Accepted Answer · answered Aug 02 '22 at 19:33

The same book (page 33) says:

Even more important is to realize that in many applications the faces of the subdivision carry no interesting meaning (think of the network of rivers or roads that we looked at before). If that is the case, we can completely forget about the face records, and the IncidentFace() field of half-edges. As we will see, the algorithm of the next section doesn’t need these fields (and is actually simpler to implement if we don’t need to update them).

So, you don't need to modify the incidentFace field in any half-edges after each diagonal insertion - you will be able to find vertices of all the monotone polygons using the next field of the HalfEdge record after all the necessary diagonals are inserted into the DCEL.

The most intricate job here is to set next and prev fields of newly inserted half-edges, and to modify these fields in existing half-edges. Exactly four existing half-edges need to be updated after each insertion - but it's not easy to find them.

As you already know, each DCEL vertex record contains a field, pointing to any half-edge, originating in this vertex. If you keep this field pointing to an internal half-edge or most recently inserted half-edge, then it'll be a little bit easier to find half-edges, which need updates in their next and prev fields after each insertion.

Thanks! I've been working on this for days. It's not easy. As your answer suggests, I have dropped the faces, and that helps. As far as the other trickiness, I've been storing `HalfEdges` instead of `Vertexes` for some things (like in the priority queues, helper map, stack). So the `edge.origin` is the vertex that I would store if I were following the book algorithm exactly. Using `HalfEdges` like this helps keep track of which face I'm working on, but then this leads to some other complications. So I may try your suggestion in the last paragraph too. — Rob N, Aug 03 '22 at 16:22
Maybe this should be another question, but I'm also curious about this line in the book (ch3, p.52): _we store the edges of P intersecting the sweep line in the leaves of a dynamic binary search tree T_. I'm familiar with binary search trees, like red black trees. But in this case the comparison keys are changing as the scan line moves. Is a "_dynamic_ binary search tree" a special kind of data type that deals with this? I see you can get away with a normal BST, and a mutating key comparator, because the edges don't change order, _unless_ something degenerate happens like crossing edges. — Rob N, Aug 03 '22 at 18:12
Please see: https://stackoverflow.com/questions/64908672/sweep-line-polygon-triangulation-how-to-find-edge-left-to-current-vertex — HEKTO, Aug 03 '22 at 22:02

How to add a diagonal to a doubly-connected edge list in constant time?

1 Answers1