The quad-edge data structure (Delaunay/Voronoi)

Question

2 questions for the computational geometers or algebraists:

I am just beginning to dive into computational geometry and I am loving it =)

I am attempting to read the famous article by Guibas and Stolfi called "Primitives for the manipulation of general subdivisions and the computation of Voronoi Diagrams" in order to implement a Delaunay triangulation algorithm. I am tempted to skip all the theoretical stuff and just read the description of their quad-edge data structure to save time. However, I think it may be worth it to understand all the math in the article if the structure is widely used, or just because it may be beautiful.

The math is a little to dense for me. I'm not completely ignorant on topology, but the description of their edge algebra requires knowledge of abstract algebra that I don't have.

My two questions are: What other applications of the quad-edge structure are there besides computing Delaunay/Voronoi? It seems like an extremely powerful tool.

The second question; What is an abstract algebra? It would be great if you could give me a reference to an introduction to abstract algebra, just enough so I can understand the section on their edge algebra.

Thank you!

Answer 1

I think Guibas and Stolfi's “edge algebra” formalism is a bit unnecessary.

All that's really necessary is to remember the distinction between primal and dual graphs. Each face $f$ of the primal graph has a corresponding dual vertex $f^*$; each edge $e$ of the primal graph has a corresponding dual edge $e^*$; and each vertex $v$ of the primal graph has a corresponding dual face $v^*$. Primal edges connect primal vertices and separate primal faces; dual edges connect dual vertices and separate dual faces. The dual of the dual of anything is the original thing. See Figure 4 in Guibas and Stolfi's paper:

Guibas and Stolfi propose thinking about each edge (either primal or dual) as a collection of four directed, oriented edges; for simplicity, I'll call these darts. Each dart $\vec{e}$ points from one endpoint $\text{tail}(\vec{e})$ to the other endpoint $\text{head}(\vec{e})$, and locally separates two faces $\text{left}(\vec{e})$ and $\text{right}(\vec{e})$. The choice of which endpoint to call $\text{tail}(\vec{e})$ is the dart's direction, and the choice of which face to call $\text{left}(\vec{e})$ is its orientation. (Guibas and Stolfi use “Org” and “Dest” instead of “tail” and “head”, but I prefer the shorter labels, because Unnecessary Abbreviations Are Evil.)

For any dart $\vec{e}$, Guibas and Stolfi associate three related darts:

1. $\text{tailNext}(\vec{e})$: The dart leaving $\text{tail}(\vec{e})$ next in counterclockwise order after $\vec{e}$.
2. $\text{flip}(\vec{e})$: The “same” dart as $\vec{e}$, but with $\text{left}(\vec{e})$ and $\text{right}(\vec{e})$ swapped.
3. $\text{rotate}(\vec{e})$: The dual dart obtained by giving $\vec{e}$ a quarter turn counterclockwise around its midpoint.

These three functions satisfy all sorts of wonderful identities, like the following:

• $\text{right}(\text{tailNext}(\vec{e})) = \text{left}(\vec{e})$
• $\text{right}(\text{flip}(\vec{e})) = \text{left}(\vec{e})$
• $\text{right}(\text{rotate}(\vec{e})) = \text{head}(\vec{e})^*$
• $\text{flip}(\text{flip}(\vec{e})) = \vec{e}$
• $\text{rotate}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))) = \vec{e}$
• $\text{tailNext}(\text{rotate}(\text{tailNext}(\text{rotate}(\vec{e})))) = \vec{e}$

For a complete list, see page 83 of the paper (but beware that the authors use postfix notation $e~Flip$, presumably because it's closer to the declarative code e.Flip). Guibas and Stolfi call any triple of functions satisfying all these identities an edge algebra.

Moreover, given these three functions, one can define several other useful functions like

• $\text{reverse}(\vec{e}) = \text{rotate}(\text{flip}(\text{rotate}(\vec{e})))$ — swap head and tail vertices
• $\text{leftNext}(\vec{e}) = \text{rotate}(\text{tailNext}(\text{rotate}(\text{rotate}(\text{rotate}(\vec{e})))))$ — the next dart after $\vec{e}$ in counterclockwise order around the face $\text{left}(\vec{e})$

Finally, knowing these functions tell you absolutely everything about the topology of the subdivision, and any polygonal subdivision of any surface (orientable or not) can be encoded using these three functions.

The quad-edge data structure is a particularly convenient representation of a surface graph that provides access to all these functions, along with several other constant-time operations like inserting, deleting, contracting, expanding, and flipping edges; splitting or merging vertices or faces; and adding or deleting handles or cross-caps.

Have fun!