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

\def\InCircle{\hbox{\it InCircle}}
\def\lcand{\hbox{\it lcand}}
\def\rcand{\hbox{\it rcand}}
\def\basel{\hbox{\it basel}}
\def\CCW{\hbox{\it CCW}}
\def\cross{\hbox{\it cross}}
\def\ldi{\hbox{\it ldi}}
\def\rdi{\hbox{\it rdi}}
\def\quadedge{quad edge}
\def\B{\hbox{\curfont W B\/}} % for B↑2
\def\S{\hbox{\curfont W S\/}} % for S↑1

\def\thin{\hskip0.7pt}
\def\sym{\thin\hbox{\it Sym\/}}
\def\flip{\thin\hbox{\it Flip\/}}
\def\rot{\thin\hbox{\it Rot\/}}
\def\onext{\thin\hbox{\it Onext\/}}
\def\oprev{\thin\hbox{\it Oprev\/}}
\def\dnext{\thin\hbox{\it Dnext\/}}
\def\dprev{\thin\hbox{\it Dprev\/}}
\def\lnext{\thin\hbox{\it Lnext\/}}
\def\lprev{\thin\hbox{\it Lprev\/}}
\def\rnext{\thin\hbox{\it Rnext\/}}
\def\rprev{\thin\hbox{\it Rprev\/}}
\def\lef{\thin\hbox{\it Left\/}}
\def\rif{\thin\hbox{\it Right\/}}
\def\org{\thin\hbox{\it Org\/}}
\def\dest{\thin\hbox{\it Dest\/}}
\def\dual{\thin\hbox{\it Dual\/}}

\def\psym{\hbox{\fx .Sym}}
\def\pflip{\hbox{\fx .Flip}}
\def\prot{\hbox{\fx .Rot}}
\def\ponext{\hbox{\fx .Onext}}
\def\poprev{\hbox{\fx .Oprev}}
\def\pdnext{\hbox{\fx .Dnext}}
\def\pdprev{\hbox{\fx .Dprev}}
\def\plnext{\hbox{\fx .Lnext}}
\def\plprev{\hbox{\fx .Lprev}}
\def\prnext{\hbox{\fx .Rnext}}
\def\prprev{\hbox{\fx .Rprev}}
\def\plef{\hbox{\fx .Left}}
\def\prif{\hbox{\fx .Right}}
\def\pnext{\hbox{\fx .Next}}
\def\pdata{\hbox{\fx .Data}}
\def\porg{\hbox{\fx .Org}}
\def\pdest{\hbox{\fx .Dest}}

\abstract{We discuss the following problem: given $n$ points in the plane (the ``sites’’), and an arbitrary query point $q$, find the site that is closest to $q$. This problem can be solved by constructing the Voronoi diagram of the given sites, and then locating the query point in one of its regions. We give two algorithms, one that constructs the Voronoi diagram in $O(n\lg n)$ time, and another that inserts a new site in $O(n)$ time. Both are based on the use of the Voronoi dual, the Delaunay triangulation, and are simple enough to be of practical value. The simplicity of both algorithms can be attributed to the separation of the geometrical and topological aspects of the problem, and to the use of two simple but powerful primitives, a geometric predicate and an operator for manipulating the topology of the diagram. The topology is represented by a new data structure for generalized diagrams, that is embeddings of graphs in two-dimensional manifolds. This structure represents simultaneously an embedding, its dual, and its mirror-image. Furthermore, just two operators are sufficient for building and modifying arbitrary diagrams.}

One of the fundamental data structures of computational geometry is the Voronoi diagram. This diagram arises from consideration of the following natural problem. Let $n$ points in the plane be given, called {\it sites}. We wish to preprocess them into a data structure, so that given a new query point $q$, we can efficiently locate the nearest neighbor of $q$ among the sites. The $n$ sites in fact partition the plane into a collection of $n$ regions, each associated with one of the sites. If region $P$ is associated with site $p$, then $P$ is the locus of all points in the plane closer to $p$ than to any of the other $n-1$ sites. This partition is known as the {\it Voronoi} diagram (or the {\it Dirichlet}, or {\it Thiessen}, tesselation) determined by the given sites.

The closest site problem is can therefore be solved by constructing the Voronoi diagram, and then locating the query point in it. Using the currently best available algorithms, the Voronoi diagram of $n$ points can be computed in $O(n\lg n)$ time and stored in $O(n)$ space; these bounds have been shown to be optimal in the worst case [\Sham]. Once we have the Voronoi diagram, we can construct in linear further time a structure with which we can do point location in a planar subdivision in $O(\lg n)$ time [\Kirki].

Shamos [\Sham] first pointed out that the Voronoi diagram can be used as a powerful tool to give efficient algorithms for a wide variety of other geometric problems. Given the Voronoi, we can compute in linear time the closest pair of sites, or the closest neighbor of each site, or the Euclidean minimum spanning tree of the $n$ sites, or the largest point-free circle with center inside their convex hull, etc. Several of these problems are known to require $\Omega(n\lg n)$ time in the worst case, so these Voronoi-based algorithms are asymptotically optimal.

The complexity of the $O(n\lg n)$ Voronoi algorithms that can be found in the literature is a serious barrier to their widespread utilization. To the authors’ knowledge, they so far have never been used in any of the significant practical applications of closest-point problems in statistics, operations research, geography, and other areas. In every case the authors of those programs chose to use asymptotically slower $O(n↑2)$ algorithms, which were much simpler to code and almost certainly faster for the ranges of interest in $n$. Furthermore, the presentation of Voronoi algorithms in the literature has often been insufficiently precise. Authors typically confine themselves only to a very high-level description of their algorithms. As with many geometric problems, difficulties can arise in the implementation when degeneracies occur, as for example when three of the given points happen to be cocircular.

In this paper we present a novel way of looking at the standard Voronoi computation techniques, such as the divide and conquer [\ShamHo] and incremental [\GrSi] methods, that results in Voronoi algorithms that are very concise and substantially easier to read, implement and verify. One of the main reasons for this simplicity is that we work with the duals of the Voronoi diagrams, which are known as {\it Delaunay triangulations}, rather than with the diagrams themselves. The other major reason is the clean separation that we are able to make between topological and geometrical aspects of the problem. In sections 6 through 10 we show that the hardest part of constructing a Voronoi diagram or Delaunay triangulation is the determination of its topological structure, that is, the incidence relations between vertices, edges, and faces. Once the topological properties of the diagram are known, the geometrical ones (coordinates, angles, lengths, etc.) can be computed in time linear in the size of the diagram.

Our algorithms are built using essentially two primitives: a geometric predicate, and a topological operator for manipulating the structure of the diagrams. The geometrical primitive, that we call the {\InCircle} test, encapsulates the essential geometric information that determines the topological structure of the Voronoi diagram, and is a powerful tool not only in the coding of the algorithms but also in proving their correctness. As evidence for its importance, we show that it possesses many interesting properties, and can be defined in a number of equivalent ways.\par

The topological structure of a Voronoi or Delaunay diagram is equivalent to that of a particular embedding of some undirected graph in the Euclidean plane. We have found it convenient to consider such diagrams as being drawn on the sphere rather than on the plane; topologically that is equivalent to augmenting the Euclidean plane by a dummy {\it point at infinity}. This allows us to represent such things as infinite edges and faces in the same way as their finite counterparts. In sections 1 through 5 we will establish the mathematical properties of such embeddings, define a notation for talking about them, and describe a data structure for their representation.

It turns out that the data structure we propose is general enough to allow the representation of undirected graphs embedded in arbitrary two-dimensional manifolds. In fact, it may be seen as a variant of the ``winged edge’’ representation for polyhedral surfaces [\Baum]. We show that a single topological operator, which we call {\it Splice}, together with a single primitive for the creation of isolated edges, is sufficient for the construction and modification of arbitrary diagrams. Our data structure has the ability to represent simultaneously and uniformly both the primal, the dual, and the mirror-image diagrams, and to switch arbitrarily from one of these domains to another, in constant time. Finally, the design of the data structure enables us to manipulate its geometrical and topological parameters independently of each other. As it will become clear in the sequel, these properties have the effect of producing programs that are at once simple, elegant, efficient from a practical point of view, and asymptotically optimal in time and space.

Since this paper is quite long, some guidance to the forthcoming sections may be advisable. Section 1 introduces the concept of a simple subdivision of a manifold and discusses some of the conventions we adopt as compared to the extant literature. Section 2 presents the very important ideas of the dual of a subdivision, and the edge algebra associated with a subdivision. The edge algebra is a combinatorial structure on the edges of the subdivision that we claim captures all the topological information associated with the subdivision. Section 3 is more technical and may be omitted on a first reading. It formalizes and then proves the above claim about edge algebras by showing that isomorphism of edge algebras is equivalent to topological homeomorphism between the corresponding subdivisions. In section 4 we present a computer representation for an edge algebra, which is our {\it quad edge} data structure. Section 5 introduces the topological primitives that we use to manipulate this structure and discusses their properties and implementation. Section 6 tailors these primitives to the application on hand, namely the Delaunay/Voronoi computation. Section 7 reviews some properties of the Voronoi/Delauanay subdivision and section 8 presents our main geometric primitive for their computation, the {\InCircle} test and its properties. Section 9 presents in detail and proves correct a divide and conquer algorithm for Voronoi computations, and section 10 discusses incremental techniques.

In this section we will give a precise definition for the informal concept of an embedding of an undirected graph on a surface. Special instances of this concept are sometimes referred to as a subdivision of the plane, a generalized polyhedron, a two-dimensional diagram, or by other similar names. They have been extensively discussed in the solid modeling literature of computer graphics [\Baum, \MaSu]. We want a definition that accurately reflects the topological properties one would intuitively expect of such embeddings (for instance, that every edge is on the boundary of two faces, every face is bounded by a closed chain of edges and vertices, every vertex is surrounded by a cyclical sequence of faces and edges, and so forth) and at the same time is as general as possible and leads to a clean theory and data structure.

We assume the reader is familiar with a few basic concepts of point-set topology, such as topological space, continuity, and homeomomorphism [\IyKa]. Two subsets $A$ and $B$ of a topological space $M$ are said to be {\it separable} if some neighborhood of $A$ is disjoint from some neighborhood of $B$; otherwise, they are said to be {\it incident} on each other. A {\it line} of $M$ is a subspace of $M$ homeomorphic to the open interval $\B↑1=(0\span 1)$ of the real line. A {\it disk} of $M$ is a subspace homeomorphic to the open circle of unit radius $\B↑2=\rset{x\in\reals↑2\,:\, \leftv x\rightv<1}$. Recall that a {\it two-dimensional manifold} is a topological space with the property that every point has an open neighborhood which is a disk (all manifolds in this paper will be two-dimensional).

\definition{1.1}{A {\it subdivision} of a manifold $M$ is a partition $S$ of $M$ into three finite collections of disjoint parts, the {\it vertices}, the {\it edges}, and the {\it faces} (denoted respectively by $\Vscr S$, $\Escr S$, and $\Fscr S$), with the following properties:
$$\vbox{\halign{\hskip 20pt #\quad|\lft{#}\cr
S1.|Every vertex is a point of $M$.\cr\va
S2.|Every edge is a line of $M$.\cr\va
S3.|Every face is a disk of $M$.\cr\va
S4.|The boundary of every face is a closed path\cr
\null|of edges and vertices.\cr}}$$
}

Condition S4 needs some explanation. We will denote by $\clos{\B}\null↑2$ the {\it closed} circle of unit radius, and by $\S↑1$ its circumference. Let us define a {\it simple path} in $\S↑1$ as a partition of $\S↑1$ into a finite sequence of isolated points and open arcs. The precise meaning of S4 is then the following: for every face $F$ there is a simple path $\pi$ in $\S↑1$ and a continuous mapping $\phiF̌$ from $\clos{\B}\null↑2$ onto the closure of $F$ that (i) maps homeomorphically $\B↑2$ onto $F$, (ii) maps homeomorphically each arc of $\pi$ into an edge of $S$, and (iii) maps each isolated point of $\pi$ to a vertex of $S$.

Condition S4 has a number of important implications. Clearly the points and arcs of $\pi$ must alternate as we go around $\S↑1$; if $\alpha$ is the arc between two consecutive points $a$ and $b$ of $\pi$, then its image $\phiF̌(\alpha)$ is an edge incident to the points $\phiF̌(a)$ and $\phiF̌(b)$. Therefore, the images of the elements of $\pi$, taken in the order in which they occur around $\S↑1$, constitute a closed, connected path $\piF̌$ of edges and vertices of $S$, whose union is the boundary of $F$. Notice that the bounding path $\piF̌$ need not be simple, since $\phiF̌$ may take two or more distinct arcs or points of $\pi$ to the same element of $S$. Therefore the closure of a face may not be homeomorphic to a disk, as figure 1.1 shows.

Since it is impossible to cover a disk with only a finite number of edges and vertices, every edge and every vertex in a subdivision of a manifold must be incident to some face. We conclude that every edge is entirely contained in the boundary of some face, and that it is incident to two (not necessarily distinct) vertices of $S$. These vertices are called the {\it endpoints} of the edge; if they are the same, then the edge is a {\it loop}, and its closure is homeomorphic to the circle $\S↑1$.

Since every element of $S$ is in the closure of some face, and since the closed disk $\clos{\B}↑2$ is compact, the manifold $M$ is the union of a finite number of compact sets --- and therefore is itself compact. In fact, condition S4 can be replaced by the requirement that $M$ be compact, that the edges be pairwise separable, and that every vertex is incident to some edge. Furthermore, every compact manifold has a subdivision. We will not attempt to prove these statements, since they are too technical for the scope of this paper.

Informally speaking, a compact two-dimensional manifold is a surface that closes upon itself, has no boundary, and in which every infinite sequence has an accumulation point. The sphere, the torus, and the projective plane are such manifolds; the disk, the line segment, the whole plane, and the M\uo bius strip are not. The compactness condition is not as restrictive as it may seem; any manifold can be made compact by adding a dummy ``point at infinity’’ that is by definition an accumulation point of all sequences with no other accumulation points. This operation transforms the Euclidean plane $\reals↑2$ into the {\it extended plane}, which is homeomorphic to the sphere.

The collection of all edges and vertices of a subdivision $S$ constitutes an undirected graph, the {\it graph of $S$}. The graphs of two equivalent subdivisions $S$ and $S\pr$ are obviously isomorphic. The converse is not always true: if $S$ and $S\pr$ have isomorphic graphs, it doesn’t follow that they are equivalent, or that $M$ and $M\pr$ are homeomorphic. Figure 1.2 shows an example. Note that the subdivisions are not equivalent even though there also is a one-to-one correspondence between the faces of $S$ and $S\pr$ with the property that corresponding faces are incident to corresponding edges and vertices. This example shows that the {\it set} of edges and vertices on the boundary of a face is not enough information to characterize its relationship to the rest of the manifold.

This fact is the main source of complexity in the theoretical treatment of subdivisions, notably in the proof that our data structure is a consistent representation of a general subdivision. It is possible to define subdivisions in such a way that their topological structure is completely determined by that of their graphs. For example, if the manifold is restricted to be a sphere, and the graph is triply connected [\Har], then the subdivision is determined up to equivalence. However, any set of conditions strong enough to achieve this goal would probably outlaw ``degeneracies’’ such as loops, multiple edges with the same endpoints, faces with nonsimple boundaries, and so forth. Subdivisions with such degeneracies are much more common than it may seem: they inevitably arise as intermediate objects in the transformation of a ``well-behaved’’ subdivision into another. An even stronger reason for adopting our liberal definition is that it leads to more flexible data structures and simpler atomic operations with weaker preconditions.

On the other hand, we depart from the common solid modeling tradition by insisting that every face be a simple disk, without ``handles’’ or ``holes’’, even though the whole manifold is allowed to have arbitrary connectivity. The main reason for this requirement is to enable a clean and unambiguous definition of the dual subdivision (see subsection 2.2). One important consequence of this restriction is stated below:

\theorem{1.1}{The graph of a simple subdivision is connected iff the manifold is connected.}
\proof{Since every face is incident to some edge, if the graph is connected then the whole manifold is too. Now assume the the graph is not connected, but the manifold is. Since the faces are pairwise separable, and their addition to the graph makes it connected, some face is incident to two distinct components of the graph. By condition S4 the boundary of that face is connected, a contradiction.}

In this section we will develop a convenient notation for describing relationships among edges of a subdivision, and a mathematical framework that will justify the choice of our data structure. We will develop first the theory and representation for arbitrary compact manifolds, and then we will show that certain important simplifications can be made in the particular case when the manifold is orientable. For many applications, including the computation of Voronoi diagrams, the only relevant manifold will be the extended plane.

On any disk $D$ of a manifold there are exactly two ways of defining a local ``clockwise’’ sense of rotation; these are called the two possible {\it orientations} of $D$. An {\it oriented element} of a subdivision $P$ is an element $x$ of $P$ together with an orientation of a disk containing $x$. There are also exactly two consistent ways of defining a linear order among the points of a line $\lscr$; each of these orderings is called a {\it direction along} $\lscr$. A {\it directed edge} of a subdivision $P$ is an edge of $P$ together with a direction along it. Since directions and orientations can be chosen independently, for every edge of a subdivision there are four directed, oriented edges. Observe that this is true even if the edge is a loop, or is incident twice to the same face of $P$.

For any oriented and directed edge $e$ we can define unambiguously its vertex of {\it origin}, $e\org$, its {\it destination}, $e\dest$, its {\it left face}, $e\lef$, and its {\it right face}, $e\rif$. We define also the {\it flipped} version $e\flip$ of an edge $e$ as being the same unoriented edge taken with {\it opposite orientation} and same direction, as well as the {\it symmetric} of $e$, $e\sym$, as being the same undirected edge with the {\it opposite direction} but the same orientation as $e$. We can picture the orientation and direction of an edge $e$ as a small bug sitting on the surface over the midpoint of the edge and facing along it. Then the operation $e\sym$ corresponds to the bug making a half turn on the same spot, and $e\flip$ corresponds to the bug hanging upside down from the other side of the surface, but still at the same point of the edge and facing the same way.

The elements $e\org$, $e\lef$, $e\rif$, and $e\dest$ are taken by definition with the orientation that agrees locally with that of $e$. More precisely, the orientation of $e\org$ agrees with that of some initial segment of $e$, and that of $e\dest$ agrees with some final segment of $e$. Note that for some loops $e\org$ and $e\dest$ may have opposite orientations, in spite of being the same (unoriented) vertex. Similarly, the orientation of $e\lef$ agrees with $e$ along the ``left margin’’ of $e$, and that of $e\rif$ agrees along its ``right margin’’. If $e$ is a bridge, it may be the case that $e\lef$ and $e\rif$ have different orientations, in spite of being the same (unoriented) face. By extending our previous notation, we will denote by $VS$, $ES$ and $FS$ the sets of directed and oriented elements of a subdivision $S$. In the rest of this section, unless otherwise specified, all subdivision elements are assumed to be oriented, and directed if edges.

A sufficiently small disk containing the vertex $v=e\org$, it can be mapped homeomorphically onto the unit disk $\B↑2$ in such a way that $v$ is mapped to the origin, and the intersection of $D$ with every edge incident to $v$ is a ray of $\B↑2$. Traversing the boundary of $D$ in the counterclockwise direction (as defined by the orientation of $v$) establishes a cyclical ordering of those edges. If each edge is oriented so as to agree with $v$, and directed away from $D$, we obtain what is called the {\it ring of edges out of $v$}. We can define the {\it next edge with same origin}, $e\onext$, as the one immediately following $e$ (counterclockwise) in this ring (see figure 2.1). Note that if $e$ is a loop it will occur twice in the ring of edges out of $v$. To be precise, both $e$ and an oppositely directed version of it (either $e\sym$ or $e\sym\flip$) will occur once each: since the manifold around $v$ is like a disk, $e$ will occur only once in each circuit, and we will never encounter $e\flip$.

Similarly, given an edge $e$ we define the {\it next counterclockwise edge with same left face}, denoted by $e\lnext$, as being the first edge we encounter after $e$ when moving along the boundary of the face $F=e\lef$, in the counterclockwise sense as determined by the orientation of $F$. The edge $e\lnext$ is oriented and directed so that $e\lnext\lef=F$ (including orientation). The successive images of $e$ under $\lnext$ give precisely the edges of the bounding path $\piF̌$ of condition S4 (in one of the two possible orders). As in the case of $\onext$, the edge $e$ appears exactly once in this list, and either $e\sym$ or $e\flip$ (but not $e\sym\flip$) may appear once.

\definition{2.1}{Two subdivisions $S$ and $S↑\ast$ are said to be {\it dual} of each other if for every directed and oriented edge $e$ of either subdivision there is another edge $e\dual$ of the other such that
$$\vbox{\halign{\hskip20pt #|\quad $ # $|\lft{$\null= # $}\cr
D1.|(e\dual)\dual|e\cr\va
D2.|(e\sym)\dual|(e\dual)\sym\cr\va
D3.|(e\flip)\dual|(e\dual)\flip\sym\cr\va
D4.|(e\lnext)\dual|(e\dual)\onext↑{-1}\cr}}\hfill$$
}

Equation D4 states that moving counterclockwise around the left face of $e$ in one subdivision is the same as moving clockwise around the origin of $(e\dual)$ in the other subdivision. To see why, note that the edges on the boundary of the face $F=e\lef$, in counterclockwise order, are $\seq{e\lnext, e\lnext↑2, \ldots, e\lnext↑m=e}$ for some $m\geq 1$. This path maps through $\dual$ to the sequence $\seq{(e\dual)\onext↑{-1}, (e\dual)\onext↑{-2}, \ldots, (e\dual)\onext↑{-m}=e\dual}$ of all edges coming out of the vertex $v=(e\dual)\org$ of $S↑\ast$, in clockwise order around $v$.

We can therefore extend $\dual$ to vertices and faces of the two subdivisions, by defining $(e\lef)\dual=(e\dual)\org$ and $(e\org)\dual=(e\dual)\lef$. Equations D2 and D3 imply that any two edges that differ only in orientation and direction will be mapped to two versions of the same undirected edge. Combining this with the preceding argument we conclude that $\dual$ establishes a correspondence between $ES$ and $ES↑\ast$, between $VS$ and $FS↑\ast$, and between $FS$ and $VS↑\ast$, such that incident elements of $S$ correspond to incident elements of $S↑\ast$, and vice-versa. It follows that two vertices of one subdivision are connected by an edge whenever (and as many times as) the corresponding faces of the other are incident to a common edge. So, in the particular case when $S$ and $S↑\ast$ are subdivisions of the sphere, the graphs of $S$ and $S↑\ast$ are duals of each other in the sense of graph theory.

Figure 2.2 shows a subdivision of the extended plane (solid lines) superimposed on its dual (dotted lines). Note that the two subdivisions of figure 2.2 have the property that each undirected edge of one meets (and crosses) only the corresponding dual edge of the other, and that each vertex of one is in the corresponding dual face of the other. When this happens, we say that $S$ and $S↑\ast$ are {\it strict duals} of each other. In that case, the dual of an oriented and directed edge $e$ is the edge of the dual subdivision that crosses $e$ from left to right, but taken with orientation {\it opposite} to that of $e$. That is, the dual subdivision should be looked from the other side of the manifold, or the manifold should be turned inside out. This reflects the correspondence between counterclockwise traversal of $e\lef$ to clockwise traversal of $(e\dual)\org$.

This implicit ``flipping’’ of the manifold is unavoidable if $S$ and $S↑\ast$ are superimposed as strict duals and we insist that $\dual$ be its own inverse. It has the serious drawback of making the calculus of the edge functions much less intuitive. It is therefore preferable to relate the two dual subdivisions by means of the function
$$e\rot=e\flip\dual=e\dual\flip\sym$$
which maps $ES$ to $ES↑\ast$ without this implicit ``flipping’’. The edge $e\rot$ is called the {\it rotated} version of $e$; it is the undirected dual of $e$, directed from $e\rif$ to $e\lef$, and oriented so that moving counterclockwise around the right face of $e$ corresponds to moving counterclockwise around the origin of $e\rot$. If the two subdivisions are superimposed as strict duals, like in figure 2.2, then we may say that $e\rot$ is $e$ ``rotated $90\deg$ counterclockwise’’ around the crossing point. In fact, the only reason for not defining duality in terms of $\rot$ (rather than $\dual$) is that it fails short of being its own inverse: $(e\rot)\rot$ gives $e\sym$ instead of $e$.

The functions $\flip$, $\rot$, and $\onext$ satisfy the following properties:
$$\vbox{\halign{\hskip20pt #\quad|\lft{#}\hfill\cr
E1.|$e\rot↑4=e$\cr\va
E2.|$e\rot\onext\rot\onext=e$\cr\va
E3.|$e\rot↑2\neq e$\cr\va
E4.|$e\in ES$\ \ iff\ \ $e\rot\in ES↑\ast$\cr\va
E5.|$e\in ES$\ \ iff\ \ $e\onext\in ES$\cr\vc
F1.|$e\flip↑2=e$\cr\va
F2.|$e\flip\onext\flip\onext=e$\cr\va
F3.|$e\flip\onext↑n\neq e$\ \ for any $n$\cr\va
F4.|$e\flip\rot\flip\rot=e$\cr\va
F5.|$e\in ES$ iff $e\flip\in ES$\cr
}}\hfill$$

A number of useful properties can be deduced from these, as for example
$$\vbox{\halign{\hskip20pt\lft{$ # $}|\lft{$\null = # $}\cr
e\flip↑{-1}|e\flip\cr\vb
e\sym|e\rot↑2\cr\vb
e\rot↑{-1}|e\rot↑3\cr
\null|e\flip\rot\flip\cr\vb
e\dual|e\flip\rot\cr\vb
e\onext↑{-1}|e\rot\onext\rot\cr
\null|e\flip\onext\flip,\cr
}}$$
and so forth. For added convenience in talking about subdivisions, we introduce some derived functions. By analogy with $e\lnext$ and $e\onext$, for a given $e$ we define the {\it next edge with same right face}, $e\rnext$, and {\it with same destination}, $e\dnext$, as the first edges that we encounter when moving counterclockwise from $e$ around $e\rif$ and $e\dest$, respectively. These functions satisfy also the following equations:
$$\vbox{\halign{\hskip20pt\lft{$ # $}|\lft{$\null= # $}\cr
e\lnext|e\rot↑{-1}\onext\rot\cr\vb
e\rnext|e\rot\onext\rot↑{-1}\cr\vb
e\dnext|e\sym\onext\sym\cr
}}$$

The orientation and direction of the returned edges is defined so that $e\lnext\lef=e\lef$, $e\rnext\rif=e\rif$, and $e\dnext\dest=e\dest$. Note that $e\rnext\dest= e\org$, rather than vice-versa. By moving {\it clockwise} around a fixed endpoint or face, we get the inverse functions, defined by
$$\vbox{\halign{\hskip20pt\lft{$ # $}|\lft{$\null= # $}|\lft{$\null= # $}\cr
e\oprev|e\onext↑{-1}|e\rot\onext\rot\cr\vb
e\lprev|e\lnext↑{-1}|e\onext\sym\cr\vb
e\rprev|e\rnext↑{-1}|e\sym\onext\cr\vb
e\dprev|e\dnext↑{-1}|e\rot↑{-1}\onext\rot↑{-1}\cr
}}$$

The axioms imply that $\rot$ is a bijection from $E$ to $E↑\ast$ and from $E↑\ast$ to $E$. Also $\flip$ and $\onext$ each define permutations acting on $E$ and $E↑\ast$ separately. The orbits of $\onext$ in $E$ are in one-to-one correspondence with the vertices of $S$, and therefore also with the faces of $S↑\ast$. These orbits are joined by $\flip$ in pairs of opposite orientation. We can therefore define $e\org$ in an edge algebra as the orbit of $e$ under $\onext$, and similarly $e\lef=e\rot↑{-1}\org$, $e\rif=e\rot\org$, $e\dest=e\sym\org$. Notice that $e\flip\org$ is the same as $e\org\flip$ (the set obtained by $\flip$ping every element of $e\org$).

Edge algebras are a purely combinatorial abstraction of subdivisions, in the same way that undirected graphs are an abstraction of the subdivision graphs. In the next section we will defend the position that {\it all topological properties of a subdivision $S$ are accurately captured by an edge algebra}. As a consequence this algebra, which is a finite object, can be used as a computer representation of $S$. An edge algebra represents simultaneously a pair of dual subdivisions; as we remarked before, this allows us to express all our edge functions in terms of only three basic primitives, $\flip$, $\rot$, and $\onext$. Other advantages of this primal/dual representation will be encountered later on, and we will see that they are obtained at a negligible cost in storage and time.