[Cyan]<PreISLCedar>Stolfi>Papers>SubdBY.tex!1

In the present section we will show that the topological properties of an arbitrary subdivision $S$ are accurately and unambiguously represented by its associated edge algebra. The concepts and theorems developed in this section are essential for showing the consistency and completeness of the data structure but are not used in the rest of the paper, so the reader whose interest is mostly practical can skip to section 4. The major idea will be to show that a general subdivision $S$ can be fully characterized by the graph of a standard refinement of $S$, which in turn is closely related to the edge algebra of $S$.

\definition{3.1}{Let $S$ and $\Sigma$ be subdivisions of a manifold $M$. We say that $\Sigma$ is a {\it completion} of $S$ if it is a refinement of $S$ obtained by adding one vertex $cě$ on each edge $e$ and one vertex $vF̌$ in each face $F$, and then connecting $vF̌$ by new edges to every vertex (old or new) on the boundary of $F$.}

The vertices of $\Sigma$ are called {\it primal}, {\it crossing}, or {\it dual} depending on whether they lie on vertices, edges, or faces of $S$; they are denoted by $\Vscr \Sigma$, $\Cscr\Sigma$, and $\Vscr↑\ast\Sigma$, respectively. Every edge of $S$ is split by its crossing vertex in two {\it primal links} of $\Sigma$; the new edges added in each face are called {\it dual links} if they connect a dual vertex to a crossing point, and {\it skew links} if they connect a dual vertex to primal one. These links are denoted $\Lscr \Sigma$, $\Lscr↑\ast\Sigma$, and $\Kscr\Sigma$, in that order. Figure 3.1 shows a completion of a subdivision of the extended plane.

Definition 3.1 must be understood appropriately in the case of a face $F$ whose bounding path $\piF̌$ is not simple. If $\piF̌$ passes $k$ times through a vertex or crossing point $p$, then $p$ is to be connected to $vF̌$ by exactly $k$ new links, and their order around $vF̌$ should be the same as the order of the crossings around $\piF̌$. To describe this process precisely, let $\phiF̌$ be any continuous function from $\clos{\B}\null↑2$ to the closure of $F$ that establishes condition S4. Let $\pi=\seq{u1̌, \alpha1̌, u2̌, \alpha2̌, \ldots, uň, \alphaň, u{̌n+1}=u1̌}$ be the path in the circle $\S↑1$ that is mapped to $\piF̌$ by $\phiF̌$; in each arc $\alphaǐ$ there is a point $cǐ$ that is mapped to the crossing vertex of the edge $\phiF̌(\alphaǐ)$. Take $\phiF̌((0,0))$ to be the dual vertex $vF̌$; connect in $\clos{\B}\null↑2$ the origin $(0,0)$ to each $uǐ$ and to each $cǐ$ by a straight line segment, and let the images of these segments under $\phiF̌$ to be respectively the dual and skew links for the face $F$. Note that the restriction of faces to simple disks is essential for a simple and unambiguous definition of the completion.

From the definition, it is clear that every subdivision has at least one refinement which is a completion. Every face of $\Sigma$ consists of three vertices and three links, one of each kind, and therefore all distinct. An important consequence is that the closure of each face is homeomorphic to (not just the continuous image of) the sector of $\clos{\B}\null↑2$ bounded by two rays and an arc $uǐcǐ$ or $cǐu{̌i+1}$, which in turn is homeomorphic to a disk. In fact, the closure of a face of $\Sigma$ is homeomorphic to any planar triangle, with each corner mapping to a vertex and each side to a link. For this reason, we will refer to the faces of $\Sigma$ as {\it triangles}, and denote them by $\Tscr\Sigma$.

It is also apparent from the definition that every edge of $\Sigma$ has two distinct endpoints, and is incident to exactly two triangles (which may or may not lie in the same face of $S$). A completion may have more than one link connecting any given pair of vertices, but it has no loops. Every crossing vertex $cě$ is incident to exactly four links, two primal and two dual, and to four distinct triangles. The vertex $cě$ and these eight elements constitute a disk of $M$ that contains the edge $e$. It can be seen also that, given a primal link $\lscr$ and a dual link $\lscr↑\ast$ that are incident to the same (crossing) vertex, there is exactly one triangle that is incident to both $\lscr$ and $\lscr↑\ast$.

We consider the distinction between primal, dual and crossing vertices to be an integral part of the description of $\Si$, so $S$ is uniquely determined by it. We call $S$ the {\it primal subdivision} of $\Si$, denoted by $S\Si$. In the same spirit, we say that two completions $\Si1̌$ and $\Si2̌$ are equivalent only if there is a homeomorphism that maps each element of $\Si1̌$ to an element of $\Si2̌$, takes $\Vscr\Sigma1̌$ to $\Vscr\Sigma2̌$, and takes $\Vscr↑\ast\Sigma1̌$ to $\Vscr↑\ast\Sigma2̌$. Such an homeomorphism will clearly take $\Cscr\Sigma1̌$, $\Lscr\Sigma1̌$, $\Lscr↑\ast\Sigma1̌$, and $\KScr\Sigma1̌$ to the corresponding components of $\Sigma2̌$.

As it was defined, the edge algebra of a subdivision $S$ seems to depend not only on $S$ itself, but also on the choice of a dual subdivision $S\as$, and of the function $\dual$ (or $\rot$) that connects the two. The first part of our theoretical justification is the proof that such $S\as$ and $\dual$ always exist, and that the edge functions of $S$ and $S\as$ satisfy axioms E1--E5 and F1--F5.

Let $\Sigma$ be a completion on a manifold $M$. For every crossing $cě$ of $\Si$, define the {\it dual} of the (unoriented and undirected) edge $e$ of $S\Si$ as the set $e\as=\lscr1̌\un \set{cě}\un \lscr2̌$, where $\lscr1̌, \lscr2̌$ are the two dual links incident to $cě$. Denote by $\Escr↑\ast\Sigma$ the set of all such objects. Define the {\it dual} $Fv̌\as$ of a primal vertex $v$ as the union of $\set{v}$ and all elements of $\Si$ incident to $v$. Let $\Fs\as\Si$ be the set of all those objects.

\proof{Besides $v$ itself, the dual $Fv̌\as$ of a vertex $v$ contains only triangles, primal links, and skew links incident to $v$. Each link of $Fv̌\as$ is incident to exactly two distinct triangles of $Fv̌\as$, and conversely each of triangle is incident to two distinct links of $Fv̌\as$, one primal and one skew. Therefore, these links and triangles can be arranged in one or more sequences (without repetitions) $\seq{\lscr1̌, t1̌, \lscr2̌, t2̌, \ldotss, \lscrň, tň, \lscr{̌n+1}=\lscr1̌}$ where the $tǐ$ are triangles, the $\lscrǐ$ are alternately primal and skew links, and each $tǐ$ is incident to $\lscrǐ$ and to $\lscr{̌i+1}$. Each such sequence plus $v$ is a disk containing $v$; since $M$ is a manifold, there can be only one such disk.

\pp We conclude that $Fv̌\as$ is a disk of $M$. Furthermore, it is clear that we can construct a continuous function $\phi$ from the closed ball onto the closure $Fv̌\as$ that esablishes condition S4. Since a triangle or primal link cannot be incident to two distinct primal vertices, the elements of $\Fs\as\Si$ are pairwise disjoint. Clearly the elements of $\Es\as\Si$ are lines of $M$ that are pairwise disjoint, and also disjoint from the members of $\Fs\as\Si$ and $\Vs\as\Si$. Therefore $S\as\Si$ is a subdivision of $M$.}

\definition{3.2}{Let $\Si$ be a completion. Let $\rot$ be the function from $ES\Si\un ES\as\Si$ into itself defined as follows: for every edge $e\in ES\Si$, let $e\rot$ be the dual edge $e\as$ of $S\as\Si$, directed so as to cross $e$ from right to left and oriented so as to agree with the orientation of $e$ at the crossing point. Similarly, for each element $e\in ES\as\Si$ let $e\rot$ be the edge of $S\Si$ of which $e$ is the dual, directed and oriented according to the same rules with respect to $e$. The {\it standard edge algebra of $\Si$} is by definition $A\Si=(ES\Si, ES\as\Si, \onext, \rot, \flip)$}

\proof{Each oriented and directed edge $e$ of $ES\Si$ (or $ES\as\Si$) can be represented unambiguously by a pair of links $(eǒ, eř)$, where $eǒ$ is the origin half of $e$, and $eř$ is the dual (or primal) link of $\Si$ that is incident to the crossing vertex of $e$ and lies to its right. Conversely, any pair $(x, y)$ of adjacent links (one primal and one dual) corresponds to a unique edge of $ES\Si$ or $ES\as\Si$.

\pp For any link pair $(x, y)$ of this kind there is a unique triangle $T$ of $\Si$ incident to $x$ and $y$, and a unique triangle $T\pr$ sharing a skew link with $T$. Let’s call the {\it opposite} of the pair $(x, y)$ the link pair $(r, s)$ such that $r$ and $s$ are on the boundary of $T\pr$ and are of the same sort (primal/dual) as $x$ and $y$, respectively. Let $x\pr$ denote the link of the same sort (primal/dual) as $x$ and incident to the same crossing.

\pp According to this notation, we have$(a, b)\flip=(a, b\pr)$, $(a, b)\rot=(b, a\pr)$, and $(a, b)\onext=(x, y)$ where $(x, y)$ is opposite to $(a, b\pr)$. Now it is easy to check that the algebra $A\Si$ satisfies E1--E5 and F1--F5. For example, let $(x, y)$ be the opposite of $(b, a)$; then $(a, b)$ is the opposite of $(y,x)$, and we have
$$\eqalign{(a, b)\rot\onext\rot\onext
|=(b, a\pr)\onext\rot\onext\cr
\null|=(x, y)\rot\onext\cr
\null|=(y, x\pr)\onext\cr
\null|=(a, b)\cr}$$
and so forth. The function $e\dual=e\flip\rot$ satisfied D1--D4, since these conditions can be proved from E1--E5 and F1--F5. We conclude that $S\Si$ and $S\as\Si$ are (strict) duals of each other.}

\proof{Let $Aǐ=(ESǐ, ESǐ\as, \onextǐ, \rotǐ, \flipǐ)$, and let $\eta$ be the homeomorphism between the manifolds of $S1̌$ and $S2̌$ that establishes their equivalence. An orientation or direction for an element of $S1̌$ determines via $\eta$ a unique orientation or direction for the corresponding element in $S2̌$, and so $\eta$ is also a one-to-one correspondence between $ES1̌$ and $ES2̌$. From the definition of $\onext$ we can conclude that $\eta(e\onext1̌)=\eta(e)\onext2̌$ for all $e\in ES1̌$; the same holds for $\lnext$ and $\flip$.

\pp Let us now define the function $\xi$ from $ES1̌\un ES1̌\as$ to $ES2̌\un ES2̌\as$ as
$$\xi(e)=\alter{$ \eta(e)$ |if $e\in ES1̌$,\cr\vb
$\eta(e\rot1̌↑{-1})\rot2̌$|if $e\in ES1̌\as$.\cr}$$
Clearly $\xi$ is one-to-one, for $\rotǐ$ is one-to-one from $ESǐ$ to $ESǐ\as$. Let us now show that $\xi(e\onext1̌)=\xi(e)\onext2̌$. If $e\in ES$ the proof is trivial. If $e\in ES1̌\as$, then $e\onext1̌\in ES1̌\as$, and
$$\eqalign{\xi(e\onext1̌)|=\eta(e\onext1̌\rot1̌↑{-1})\rot2̌\cr
\null|=\eta(e\rot1̌↑{-1}\lprev1̌\rot1̌\rot1̌↑{-1})\rot2̌\cr
\null|=\eta(e\rot1̌↑{-1}\lprev1̌)\rot2̌\cr
\null|=\eta(e\rot1̌↑{-1})\lprev2̌\rot2̌\hbox{\quad(since $e\rot1̌↑{-1}\in ES$)}\cr
\null|=\eta(e\rot1̌↑{-1})\rot2̌\rot2̌↑{-1}\lprev2̌\rot2̌\cr
\null|=\xi(e)\onext2̌\cr}$$
The proof for $\xi(e\flip1̌)=\xi(e)\flip2̌$ is entirely similar, using $e\flip1̌=e\rot1̌↑{-1}\flip1̌\rot1̌$, and finally $\xi(e\rot1̌)=\xi(e)\rot2̌$ is trivial.}

\proof{For any completion $\Si$, we establish one-to-one mappings between certain subsets of oriented and directed edges of the the algebra $A\Si$ and the primal links, dual links, and vertices of $\Si$ in the following way. To each primal (or dual) link $\lscr$ of $\Si$ there corresponds a unique pair of primal (or dual) elements of $A\Si$ of the form $\set{e, e\flip}$; these elements are the directed and oriented edges of $S\Si$ (or $S\as\Si$) of which $\lscr$ is the ``origin’’ half. To each primal vertex of $\Si$ there corresponds an orbit of $A\Si$ under $\onext$ and $\flip$ (i.e., a set of the form $e\org\un e\org\flip$ for some edge $e$); similarly, to each crossing of $\Siǐ$ there corresponds an orbit of $A\Si$ under $\rot$ and $\flip$. These mappings are one-to-one, and a primal or dual link of $\Si$ is incident to a vertex if and only if the corresponding orbits in $A\Si$ intersect.

\pp We also associate each skew link of $\Si$ to a set of the form
$$\vbox{\halign{\rt{$ # $}|\lft{$ # $}\cr
\{|e, e\flip, e\rot↑{-1}, e\rot↑{-1}\flip,\cr
\null|f, f\flip, f\rot, f\rot\flip\}\cr}}$$
where $f=e\onext$, in the following way. There are exactly two triangles of $\Si$ incident to $s$, each incident also to a primal and to a dual link. We take $s\pr$ to be the union of the four subsets of $A\Si$ that correspond to those four links. It is easy to check that these subsets have the form above, and that $s$ is incident to a primal or dual vertex of $\Si$ if and only if an element of $s\pr$ intersects the orbit corresponding to that vertex. Conversely, every set of the form above determines a unique skew link by this rule.

\pp The isomorphism between $A\Si1̌$ and $A\Si2̌$ maps those representative subsets of $A\Si1̌$ to subsets of $A\Si2̌$ having the same form, and therefore it establishes a one-to-one correspondence $\xi$ between the primal (or dual) links and vertices of $\Si1̌$ and those of $\Si2̌$. Since intersecting subsets are mapped to intersecting subsets, $\xi$ preserves incidence. We conclude $\Si1̌$ and $\Si2̌$ are similar.}

\proof{Let $\xi$ be the isomorphism between the graphs of $\Si1̌$ and $\Si2̌$ that establishes their similarity. We will construct from it an homeomorphism $\eta$ between the manifolds of the two completions that establishes their equivalence. First we define $\eta$ on the vertices of $\Si1̌$ as being the same as $\xi$. For every link $r$ of $\Si1̌$ with endpoints $u$ and $v$, we can always find an homeomorphism $\etař$ from the closure of $r$ to that of $\xi(r)$ that takes $u$ to $\xi(u)$ and $v$ to $\xi(v)$; we define $\eta(p)=\etař(p)$ for all points $p$ of $r$. Clearly, $\eta$ is an homeomorphism of the graph of $\Si1̌$ onto that of $\Si2̌$.

\pp Since any pair of adjacent links of which one is primal and the other dual determines a unique triangle, the similarity of the two completions gives also a one-to-one correspondence between their triangles that preserves incidence. For each pair of corresponding triangles $T$ and $T\pr$ there is a homeomorphism $\etaŤ$ of $\clos{T}$ onto $\clos{T\pr}$ that agrees with $\eta$ on $\bound T$; this follows readily from the fact that both closures are homeomorphic to closed disks. So $\eta$ and all $\etaŤ$ constitute a finite collection of continuous maps of closed subsets of $M$ into $M\pr$, with the property that any two of them agree in the intersection of their domains. Their union $\eta↑*$ is therefore a continuous map from $M$ into $M\pr$. Clearly, $\eta↑*$ is one-to-one and onto, so it is an homeomorphism. By construction, it maps elements of $\Si1̌$ to elements of $\Si2̌$.}

\proof{Each face of $S\Siǐ$ is the union of a dual vertex and all elements of $\Siǐ$ that are incident to it. Each edge of $S\Siǐ$ is the union of a crossing and all (two) primal links of $\Siǐ$ incident to it. The homeomorphism $\eta$ that establishes the equivalence of the two completions preserves incidence and the primal/dual character of links and vertices, so it maps elements of $S\Si1̌$ to $S\Si2̌$, establishing their equivalence.}

Therefore, the topological structure of a subdivision is completely and uniquely characterized by its edge algebra. Theorems 3.3 and 3.6 also imply that all completions of a subdivision are equivalent, and that two subdivisions are equivalent if and only if their duals are equivalent. Therefore, the dual of a simple subdivision is unique up to equivalence.

To conclude our thoretical justification, we will show that every edge algebra corresponds to a subdivision of some manifold. This fact is of great practical importance, for it guarantees that any modification to the data structure that leaves axioms E1--E5 and F1--F5 invariant corresponds to a valid operation on manifolds.

\proof{Let $A=(E, E\as, \flip, \rot, \onext)$ be an edge algebra. We will prove this by by constructing a completion $\Si$ such that $A\Si$ is isomorphic to $A$. The manifold of $\Si$ is constructed by taking a collection of disjoint closed triangles, that will become the triangles of a completion, and ``pasting’’ their edges together as specified by $A$.

\pp Let then $U$ be the set of all {\it unoriented edges} of $A$, that is, the set of all unordered pairs $\set {e, e\flip}$ where $e\in E$. Similarly, let $U↑\ast$ denote the unoriented edges of $E↑\ast$. We define a {\it corner} of the algebra as being a pair of unoriented edges of the form $\set{\set{e, e\flip}, \set{e\rot, e\rot\flip}}$, where $e$ is an edge. Notice that there are $\leftv E\rightv$ distinct corner in the algebra, and that every unoriented edge belongs to exactly two corners. Let $\Tscr$ be a collection of $\leftv E\rightv$ disjoint closed triangles on the plane, each triangle $Tř$ associated to a unique and distinct corner $r$ of the algebra. Label the three vertices of each triangle with the symbols \prg{V}, \prg{E}, \prg{F}.

\pp For each unoriented edge $u\in U$, take the two corners $r$ and $s$ to which $u$ belongs, and identify homeomorphically the \prg{VE} sides of the two triangles $Tř$ and $Tš$ (matching \prg{V} with \prg{V} and \prg{E} with \prg{E}). That common side minus its two endpoints is the {\it primal link} corresponding to $u$. In the same manner, for every $u↑\ast\in U↑\ast$ take the two corners $r$ and $s$ intersecting $u↑\ast$, and identify the \prg{FE} sides of $Tř$ and $Tš$; the common side will become the {\it dual link} corresponding to $u↑\ast$.

\pp Finally, for every corner $r=\set{\set{e, e\flip}, \set{e\rot, e\rot\flip}}$ there is exactly one {\it opposite corner} $s=\set{\set{f, f\flip}, \set{f\rot, f\rot\flip}}$ such that $f=e\rot\onext$ and $e=f\rot\onext$. Identify the \prg{VF} sides of $Tř$ and $Tš$. Call the seam segment a {\it vertex-face link}.

\pp Clearly any point interior to a triangle has a neighborhood homeomorphic to a disk. Every side of every triangle is joined with exactly one side of a distinct triangle, so a point on a link also has a disk-like neighborhood. Now consider a vertex $v$ of some triangle, and all other points that have been identified with it; they have all the same label by construction. An \prg{E} type vertex $v$ belongs to exactly four triangles, corresponding to the corners
$$\set{\set{e\rot↑k, e\rot↑k\flip}, \set{e\rot↑k\rot, e\rot↑k\rot\flip}}$$
for $0\leq k<4$ and some edge $e$. Each triangle is pasted to the next one by a primal or dual link incident at $v$, so as to form a quadrilateral with center $v$. A \prg{V} or \prg{F} type vertex $v$ is common to $2n$ triangles (for some $n\geq 1$) corresponding to the corners $$\set{\set{eǩ, eǩ\flip}, \set{eǩ\rot, eǩ\rot\flip}}\hbox{\rm \ and}$$ $$\set{\set{eǩ\flip, eǩ}, \set{eǩ\flip\rot, eǩ\flip\rot\flip}},$$ where $eǩ=e\onext↑k$ for some edge $e$ and $0\leq k<n$. These triangles are pasted alternately by vertex-face links and primal or dual links, so as to form a $2n$-sided polygon around $v$. In all cases, the vertex $v$ has a disk-like neighborhood.

We represent a subdivision $S$ (and simultaneously a dual subdivision $S↑\ast$) by means of the {\it {\quadedge} data structure}, which is a natural computer implementation of the corresponding edge algebra. The edges of the algebra can be partitioned in groups of eight: each group consists of the four oriented and directed versions of an undirected edge of $S$, plus the four versions of its dual edge. The group containing a particular edge $e$ is therefore the orbit of $e$ under the subalgebra generated by $\rot$ and $\flip$. To build the data structure, we select arbitrarily a {\it canonical representative} in each group. Then any edge $e$ can be written as $\bar e\rot↑r\flip↑f$, where $r\in\set{0, 1, 2, 3}$, $f\in\set{0,1}$, and $\bar e$ is the canonical representative of the group to which $e$ belongs.

The group of edges containing $e$ is represented in the data structure by one {\it edge record} \prg{e}, divided into four parts \prg{e[0]} through \prg{e[3]}. Part \prg{e[$r$]} corresponds to the edge $\bar e\rot↑r$. See figure 4.1a.
A generic edge $e=\bar e\rot↑r\flip↑f$ is represented by the triplet $(\prg{e}, r, f)$, called an {\it edge reference}. We may think of this triplet as a pointer to the ``quarter-record’’ \prg{e[$r$]}, plus a bit $f$ that tells whether we should look at it from ``above’’ of from ``below’’.

Each part \prg{e[$r$]} of an edge record contains two fields, $\prg{Data}$ and $\prg{Next}$. The \prg{Data} field is used to hold geometrical and other non-topological information about the edge $\bar e\rot↑r$. This field neither affects nor is affected by the topological operations that we will describe, so its contents and format is entirely dependent on the application.

The \prg{Next} field of \prg{e[$r$]} contains a reference to the edge $\bar e\rot↑r\onext$. Given an arbitrary edge reference $(\prg{e}, r, f)$, the three basic edge functions $\rot$, $\flip$, and $\onext$ are given by the formulas
$$\vcenter{\halign{
\hskip20pt\lft{$ # $}|\lft{$\null= # $}\cr\va
(\prg{e}, r, f)\rot|(\prg{e}, r+1+2f, f)\cr\va
(\prg{e}, r, f)\flip|(\prg{e}, r, f+1)\cr\va
(\prg{e}, r, f)\onext|(\prg{e[$r+f$]\pnext})\rot↑f \flip↑f\cr
}}\eqno(1)$$
where the $r$ and $f$ components are computed modulo 4 and modulo 2, respectively. In the first expression above, note that $r+1+2f$ is congruent modulo 4 to $r+1$ if $f=0$, and $r-1$ if $f=1$; this corresponds to saying that rotating $e$ $90\deg$ counterclockwise, as seen from one side of the manifold, is the same as rotating it $90\deg$ clockwise as seen from the other side. Similarly, the third expression implies that
$$\vbox{\halign{
\hskip20pt\lft{$ # $}|\lft{$\null= # $}\cr
(\prg{e}, r, 0)\onext|\prg{e[$r+f$]\pnext}, \hbox{\quad and}\cr\vc
(\prg{e}, r, 1)\onext|
(\prg{e[$r+1$]\pnext})\rot\flip\cr\va
\null|(\prg{e}, r, 0)\rot\onext\rot\flip\cr\va
\null|(\prg{e}, r, 0)\oprev\flip\cr
}}$$
i.e., the moving counterclockwise around a vertex is the same as moving clockwise on the other side of the manifold. From these formulas it follows also that
$$\vbox{\halign{
\hskip20pt\lft{$ # $}|\lft{$\null= # $}\cr
(\prg{e}, r, f)\sym|(\prg{e}, r+2, f)\cr\va
(\prg{e}, r, f)\rot↑{-1}|(\prg{e}, r+3+2f, f)\cr\va
(\prg{e}, r, f)\oprev| (\prg{e[$r+1- f$]\pnext}) \rot↑{1-f} \flip↑f, \cr
}}$$
and so forth.

The record of an arbitrary edge belongs to four circular lists, corresponding to its two endpoints and its two faces. Figure 4.1 illustrates a portion of a subdivision and its {\quadedge} data structure. We may think of each record as belonging to four circular lists, corresponding to the two vertices and two faces incident to the edge. Note however that to traverse those lists we have to use the $\onext$ function, not just the \prg{Next} pointers. Consider for example the situation depicted in figure 4.2, where the canonical representative of edge $a$ has orientation opposite to that of the others.

The {\quadedge} data structure contains no separate records for vertices or faces; a vertex is implicitly defined as a ring of edges, and the standard way to refer to it is to specify one of its outgoing edges. This has the added advantage of specifying a reference point on its edge ring, which is frequently necessary when using the vertex as a parameter to topological operations. Similarly, the standard way of referring to a connected component of the edge structure is by giving one of its directed edges. In this way, we are also specifying one of the two dual subdivisions, and a ``starting place’’ and ``starting direction’’ on it. Therefore a subdivision referred to by the edge $e$ can be ``instantaneously’’ transformed into its dual by taking $e\rot$.

In many applications, including the Voronoi/Delaunay algorithms that we are going to discuss, all manifolds to be handled are orientable. This means we can assign a specific orientation to each edge, vertex and face of the subdivision so that any two incident elements have compatible orientations. Therefore the elements of the edge algebra can be partitioned in two sets, each closed under $\rot$ and $\onext$, and each the image of the other under $\flip$. Then we don’t need the $f$ bit in edge references, and the formulas simplify to
$$\vbox{\halign{
\hskip20pt\lft{$ # $}|\lft{$\null= # $}\cr
(\prg{e}, r)\rot|(\prg{e}, r+1)\cr\va
(\prg{e}, r)\onext|\prg{e[$r$]\pnext}\cr\vc
(\prg{e}, r)\sym|(\prg{e}, r+2)\cr\va
(\prg{e}, r)\rot↑{-1}|(\prg{e}, r+3)\cr\va
(\prg{e}, r)\oprev|(\prg{e[$r+1$]\pnext})\rot,\cr
}}$$
and so forth.

We can represent a simple subdivision (without its dual) by a ``simple edge algebra’’ that has only $\onext$ and $\sym$ as the primitive operators. Then we can get $\dnext$, $\lprev$ and $\rprev$ in constant time, but not their inverses. However, this may be adequate for some applications. We save two pointers (and perhaps two data fields) in each edge record. Note that this optimization cannot be used with $\flip$.

The storage space required by the {\quadedge} data structure, including the \prg{Data} fields, is $\leftv EP\rightv\times\null$(8 record pointers + 12 bits). The simplification for orientable manifolds reduces those 12 bits to 8. This compares favorably with the winged-edge representation [\Baum] and with the Muller-Preparata variant [\MuPr]. Indeed, all three representations use essentially the same pointers: each edge is connected to the four ``immediately adjacent’’ ones ($\onext$, $\oprev$, $\dnext$, $\dprev$), and the four \prg{Data} fields of our structure may be seen as corresponding to the vertex and face links of theirs.

Compared with the two versions mentioned above, the {\quadedge} data structure has the advantage of allowing uniform access to the dual an mirror-image subdivisions. As we shall see, this capability allows us to cut in half the number of primitive and derived operations, since these usually come in pairs whose members are ``dual’’ of each other. As an illustration of the flexibility of the {\quadedge} structure, consider the problem of constructing a diagram which is a cube joined to an octahedron: we can construct two cubes (calling twice the same procedure) and join one to the dual of the other.

The systematic enumeration of all edges in a (connected) subdivision is a straightforward programming exercise, given an auxiliary stack of size $O(\leftv EP\rightv)$ and a boolean mark bit on each directed edge [\Knuth]. With a few more bits per edge, we can do away with the stack entirely [\Even]. A slight modification of those algorithms can be used to enumerate the vertices of the subdivision, in the sense of visiting exactly one edge out of every vertex. If we take the dual subdivision, we get an enumeration of the faces. In all cases the running time is linear in the number of edges. Recall also that from Euler’s relation it follows that the number of vertices, edges, and faces of a subdivision are linearly related.

\section{5. Basic topological operators}

Perhaps the main advantage of the {\quadedge} data structure is that the construction and modification of arbitrary diagrams can be effected by as few as two basic topological operators, in contrast to the half-dozen or more required by the previous versions [\Braid, \MaSu].

Apart from orientation and direction, $e$ will be the only edge of the subdivision, and will not be a loop; we have $e\org\neq e\dest$, $e\lef=e\rif$, $e\lnext=e\rnext=e\sym$, and $e\onext=e\oprev=e$. To construct a loop, we may use \prg{$e$ \pgets\ MakeEdge[]\prot}; then we will have $e\org=e\dest$, $e\lef\neq e\rif$, $e\lnext=e\rnext=e$, and $e\onext=e\oprev=e\sym$.

The second operator is denoted by \prg{Splice[$a$, $b$]} and takes as parameters two edges $a$ and $b$, returning no value. This operation affects the two edge rings $a\org$ and $b\org$, and, independently, the two edge rings $a\lef$ and $b\lef$. In each case,

\indent\bu\ if the two rings are distinct, \prg{Splice} will combine them into one;

\indent\bu\ if the two are exactly the same ring, \prg{Splice} will break it in two separate pieces;

\indent\bu\ if the two are the same ring taken with opposite orientations, \prg{Splice} will $\flip$ (and reverse the order) of a segment of that ring.

The parameters $a$ and $b$ determine the place where the edge rings will be cut and joined. For the rings $a\org$ and $b\org$, the cuts will occur immediately {\it after} $a$ and $b$ (in counterclockwise order); for the rings $a\lef$ and $b\lef$, the cut will occur immediately {\it before} $a\rot$ and $b\rot$. Figure 5.2a illustrates this process for one of the simplest cases, when $a$ and $b$ have the same origin and distinct left faces. In this case \prg{Splice[$a$, $b$]} splits the common origin of $a$ and $b$ in two separate vertices, and joins their left faces. If the origins are distinct and the left faces are the same, the effect will be precisely the opposite: the vertices are joined and the left faces are split. Indeed, \prg{Splice} is its own inverse: if we perform \prg{Splice[$a$, $b$]} twice in a row we will get back the same subdivision.

Figure 5.2b illustrates the effect of \prg{Splice[$a$, $b$]} in the case where $a$ and $b$ have distinct left faces and distinct origins. In this case, \prg{Splice} will either join two components in a single one, or add an extra ``handle’’ to the manifold, depending on whether $a$ and $b$ are in the same component or not. The quad-edge data structure contains no mechanism to distinguish between these two cases, or to keep track automatically of the components and connectivity of the manifold. There seems to be no general way of doing this at a bounded cost per operation; on the other hand, in many applications this problem is trivial or straightforward, so it is best to solve this problem independently for each case. Figure 5.2b also illustrates the case when both left faces and origins are distinct.

In the edge algebra, the $\org$ and $\lef$ rings of an edge $e$ are the orbits under $\onext$ of $e$ and $e\onext\rot$, respectively. The effect of \prg{Splice} can be described as the construction of a new edge algebra $A\pr=(E, E↑\ast, \onext\pr, \rot, \flip)$ from an existing algebra $A=(E, E↑\ast, \onext, \rot, \flip)$, where $\onext\pr$ is obtained from $\onext$ by redefining some of its values. The modifications needed to obtain the effect described above are actually quite simple. If we let $\alpha=a\onext\rot$ and $\beta=b\onext\rot$, basically all we have to do is to interchange the values of $a\onext$ with $b\onext$ and $\alpha\onext$ with $\beta\onext$. The apparently complex behavior of \prg{Splice} now can be recognized as the familiar effect of interchanging the \prg{next} links of two circular list nodes [\Knuth].

As one may well expect, to preserve the validity of the axioms F1--F5 and E1--E5 we may have to make some additional changes to the $\onext$ function. For example, whenever we redefine $e\onext\pr$ to be some edge $f$, we must also redefine $e\flip{(\onext\pr)}↑{-1}$ to be $f\flip$, or, equivalently, $f\flip\onext\pr$ to be $e\flip$. So, \prg{Splice[$a$, $b$]} must perform at least the following changes in the function $\onext$:

$$\vcenter{\halign{\hfil\rt{$ # $}|\lft{$\null= # $}\cr
a\onext\pr|b\onext\cr
b\onext\pr|a\onext\cr\va
\alpha\onext\pr|\beta\onext\cr
\beta\onext\pr|\alpha\onext\cr\vc}
\halign{\hfil\rt{$ # $}|\lft{$\null= # $}\cr
(b\onext\flip)\onext\pr|a\flip\cr
(a\onext\flip)\onext\pr|b\flip\cr\va
(\beta\onext\flip)\onext\pr|\alpha\flip\cr
(\alpha\onext\flip)\onext\pr|\beta\flip\cr
}}\eqno(2)$$

Note that these equations reduce to $\onext\pr=\onext$ if $b=a$. Since $a\onext\pr=b\onext$, to satisfy axiom E5 we must have $a\in E$ iff $b\onext\in E$, which is equivalent to $a\in E$ iff $b\in E$. We will take this as a precondition for the validity of \prg{Splice[$a$, $b$]}: the effect of this operation is not defined if $a$ is a primal edge and $b$ is dual, or vice-versa\foot\dag{Note that if $a$ and $b$ lie in distinct subalgebras $Aǎ$ and $Ab̌$ of $A$, then the union of $Aǎ$ and the dual of $Ab̌$ is also a valid edge algebra. So, in practice we can always perform \prg{Splice[$a$, $b$]} when $a$ and $b$ lie in disjont data structures.}. Another problematic situation is when $b=a\onext\flip$: according to equations (2) we would have $a\onext\pr=a\onext\flip\onext=a\flip$, which contradicts F3. In this particular case, it is more convenient to define the effect of \prg{Splice[$a$, $b$]} as being null, i.e. $\onext\pr=\onext$. It turns out that, with only these two exceptions, the equations above always define a valid edge algebra:

\pp Now let’s show E2 holds in $A\pr$, i.e. $e\rot\onext\pr\rot\onext\pr=e$. Let $X$ be the set of edges whose $\onext$ has been changed, i.e.
$$X=\set{a, b, \alpha, \beta, a\onext\flip, b\onext\flip, \alpha\onext\flip, \beta\onext\flip}.$$
First, if $e\rot\not\in X$, then $e\rot\onext\rot\not\in X\onext\rot=X$, and so
$$\eqalign{e\rot\onext\pr\rot\onext\pr|=e\rot\onext\rot\onext\pr\cr
\null|=(e\rot\onext\rot)\onext\cr
\null|=e.\cr}$$

\pp Now assume $e\rot\in X$. Notice that \prg{Splice[$a$, $b$]} does exactly the same thing as \prg{Splice[$b$, $a$]}, \prg{Splice[$\alpha$, $\beta$]}, and \prg{Splice[$a\onext\flip$, $b\onext\flip$]}, so without loss of generality we can assume $e\rot=a$. Then
$$\eqalign{e\rot\onext\pr\rot\onext\pr|=a\onext\pr\rot\onext\pr\cr
\null|=b\onext\rot\onext\pr\cr
\null|=\beta\onext\pr\cr
\null|=\alpha\onext\cr
\null|=a\onext\rot\onext\cr
\null|=e\rot\onext\rot\onext\cr
\null|=e.\cr}$$

\pp In a similar way we can prove F2. To conclude, let us prove F3, or $e\flip{(\onext\pr)}↑n\neq e$ for all $n$. In other words, we have to show that $\flip$ always takes an $\onext\pr$ orbit to a different $\onext\pr$ orbit. It suffices to show this for the orbits of elements of $X$; in fact the symmetry of \prg{Splice} implies it is sufficient to show this for the orbit of $a$.

\pp Let $a\org=\seq{a1̌\; a2̌\; \ldots\; a{̌m-1}\; am̌(=a)}$ be the orbit of $a$ under the original $\onext$. The orbit of $a\flip$ under $\onext$ is then $a\flip\org=\seq{am̌\pr\; a{̌m-1}\pr\; \ldots\; a2̌\pr\; a1̌\pr}$, where $aǐ\pr=aǐ\flip$ for all $i$. These two orbits are disjoint; they cannot contain any of the edges $\alpha$, $\beta$, $\alpha\onext\flip$, or $\beta\onext\flip$, because they are in the dual subdivision. Furthermore, one contains $b$ if and only if the other contains $b\flip$. There are then only three cases to consider (see figure 5.3):

\pp Case 1: the edge $b$ is neither in $a\org$ nor in $a\flip\org$. Then let $b\org=\seq{b1̌\; b2̌\; \ldots\; b{̌n-1}\; bň(=b)}$ and $b\flip\org=\seq{bň\pr\;b{̌n-1}\pr\; \ldots\; b2̌\pr\;b1̌\pr}$. According to (2), we will have $am̌\onext\pr=b1̌$, $bm̌\onext\pr=a1̌$, $a1̌\pr\onext\pr=bm̌\pr$, $b1̌\pr\onext\pr=am̌\pr$. Therefore, the orbits of $a$ and $a\flip$ under $\onext\pr$ will be $a\org\pr=\seq{a1̌\; a2̌\; \ldots\; a{̌m-1}\; am̌(=a)\; b1̌\; b2̌\; \ldots\; b{̌n-1}\; bň(=b)}$ and $a\flip\org\pr=\seq{bň\pr\;b{̌n-1}\pr\; \ldots\; b2̌\pr\;b1̌\pr\;am̌\pr\; a{̌m-1}\pr\; \ldots\; a2̌\pr\; a1̌\pr}$.

\pp Case 2: the edge $b$ occurs in $a\org$. Then $b=aǐ$ for some $i$, $1\leq i\leq m$. After \prg{Splice} is executed we will have $am̌\onext\pr=a{̌i+1}$, $aǐ\onext\pr=a1̌$, $a1̌\pr\onext\pr=aǐ\pr$, and $a{̌i+1}\pr\onext\pr=am̌\pr$. If $i=m$ (i.e., if $a=b$) then $\onext\pr=\onext$ and we are done. If $i\neq m$ then under $\onext\pr$ the elements of $a\org$ and $a\flip\org$ will be split in the four orbits $b\org\pr=\seq{a1̌\;a2̌\;\ldots\;aǐ}$, $a\org\pr=\seq{a{̌i+1}\; a{̌i+2}\; \ldots\;am̌}$, $a\flip\org\pr=\seq{am̌\pr\; a{̌m-1}\pr\; \ldots\; a{̌i+1}\pr}$, and $b\flip\org\pr=\seq{aǐ\pr\;a{̌i-1}\pr\;\ldots\;a1̌}$.

\pp Case 3: the edge $b$ occurs in $a\flip\org$. Since $b\neq a\onext\flip=a1̌\pr$, we have $b=aǐ\pr$ for some $i$, $2\leq i\leq m$. After \prg{Splice} is executed we will have $am̌\onext\pr=a{̌i-1}\pr$, $aǐ\pr\onext\pr=a1̌$, $a1̌\pr\onext\pr=aǐ$, and $a{̌i-1}\onext\pr=am̌\pr$. Then the orbits of $\onext\pr$ containing those elements will be $a\org\pr=\seq{a{̌i-1}\pr\; a{̌i-2}\pr\; \ldots\; a1̌\pr\; aǐ\; a{̌i+1}\;\ldots\;a{̌m-1}\;am̌}$ and $a\flip\org\pr=\seq{am̌\pr\;a{̌m-1}\pr\;\ldots\;a{̌i+1}\pr\;a{̌i}\pr\;a1̌\; a2̌\;\ldots\;a{̌i-1}\;aǐ}$.

In terms of the data structure, the \prg{Splice} operation is even simpler. The identities $$a\onext\flip=a\onext\rot\flip\rot=\alpha\flip\rot$$ and $$\alpha\onext\flip=a\onext\rot\onext\flip=a\flip\rot$$ allow us to rewrite (2) as
$$\vcenter{\halign{\hskip20pt \rt{$ # $}|\lft{$\,\gets\, # $}| \hskip0.4cm \rt{$ # $}|\lft{$\,\gets\, # $}\cr
a\onext|b\onext|(a\flip\rot)\onext|\beta\flip\cr\va
b\onext|a\onext|(b\flip\rot)\onext|\alpha\flip\cr\vc
\alpha\onext|\beta\onext|
(\alpha\flip\rot)\onext|b\flip\cr\va
\beta\onext|\alpha\onext|
(\beta\flip\rot)\onext|a\flip\cr
}}\eqno(3)$$

Only one of the two assignments in each line of (3) is meaningful. The reason is that only one of the receiving $\onext$ fields actually exists in the structure; the value of the other is determined implicitly from existing links by the equations (1). If the $f$ bit of $a$ is 0, then $a\onext$ exists, and \prg{Splice} writes $b\onext$ into it. Otherwise $a\flip\rot$ has $f=0$, and we can assign $b\flip\rot\onext$ to $a\flip\rot\onext$. The same applies to $b$, $\alpha$ and $\beta$. Note that these assignments are simultaneous, that is, all right-hand sides are computed before any value is assigned to the left-hand-sides. In addition, these assignments should be preceded by a test of whether $b=a\onext\flip$, in which case they should not be executed at all. Note however that there is no need to check for $a=b$.

As an example of the use of \prg{Splice}, consider the operation \prg{SwapDiagonal[$e$]} that we will be using later on: given an edge $e$ whose left and right faces are triangles, the problem is to delete $e$ and connect the other two vertices of the quadrilateral thus formed (see fig 5.4).
This is equivalent to

{\prog
\ \ \ a \pgets\ e\poprev;
\ \ \ b \pgets\ e\psym\poprev;
\ \ \ Splice[e, a]; Splice[e\psym, b];
\ \ \ Splice[e, a\plnext]; Splice[e\psym, b\plnext]
\endprog}

\theorem{5.1}{An arbitrary subdivision $P$ can be transformed into a collection of $\leftv EP\rightv$ isolated edges by the application of at most $2\leftv EP\rightv$ \prg{Splice} operations.}
\proof{Let $e$ be an arbitrary edge of $P$. Then the operations \prg{Splice[$e$, $e\oprev$]} and \prg{Splice[$e\sym$, $e\sym\oprev$]} will have the effect of removing $e$ from $P$ and placing it as an isolated edge on a separate manifold homeomorphic to the sphere. By repeating this for every edge the theorem follows.}

The \prg{Data} links are not affected by (and do not affect) the \prg{MakeEdge} and \prg{Splice} operations; if used at all, they can be set and updated, at any time after the edge is created, by plain assignment statements. Since they carry no topological information, there is no need to forbid or restrict assignments to them. Usually each application imposes geometrical or other constraints on the \prg{Data} fields that may be affected by changes in the topology. Some care is required when enforcing those constraints; for example, the operation of joining two vertices may change the geometrical parameters of a large number of edges and faces, and updating all the corresponding \prg{Data} fields every time may be too expensive. However, even in such applications it is frequently the case that we can defer those updates until they are really needed (so that their cost can be amortized over a large number of \prg{Splice}s), or initialize the \prg{Data} links right from the beginning with the values they must have in the final structure.

\section{6. Topological operators for Delaunay diagrams}

In the Voronoi/Delaunay algorithms described further on, all edge variables refer to edges of the Delaunay diagram. The \prg{Data} field for a Delaunay edge $e$ points to a record containing the coordinates of its origin $e\org$, which is one of the sites; accordingly, we will use $e\porg$ as a synonym of $e\pdata$ in those algorithms. For convenience, we will also use $e\pdest$ instead of $e\psym\porg$. We emphasize again that these \prg{Dest} and \prg{Org} fields carry no topological meaning, and are not updated by the \prg{Splice} operation per se. The endpoints of the dual edges (Voronoi vertices) are neither computed nor used by the algorithms; if desired, they can be easily added to the structure, either during its construction or after it. The fields $e\prot\pdata$ and $e\prot↑{-1}\pdata$ are not used.

The topological manipulations performed by the algorithms on the Delaunay/Voronoi diagrams can be reduced to a pair of higher-level topological operators, defined here in terms of \prg{Splice} and \prg{MakeEdge}. The operation \prg{$e$ \pgets\ Connect[$a$, $b$, \hbox{\it side}]} will add a new edge $e$ connecting the destination of $a$ to the origin of $b$, across either $a\lef$ or $a\rif$ depending on the \hbox{\it side} flag. For added convenience, it will also set the \prg{Org} and \prg{Dest} fields of the new edge to $a\pdest$ and $b\porg$, respectively.