Representing Geometric Structures in d Dimensions: Topology and Order

1. Representing Geometric Structures in d Dimensions: Topology and Order

Erik Brisson¹

Department of Computer Science
University of Washington
Seattle, Washington 98195

1.1. Abstract

We develop a representation for the topological structure of subdivided manifolds (with and without boundary) of dimension $d \geq 1$ which allows straightforward access of the available order information. It is shown that there exists a large amount of ordering information in subdivided manifolds: given a $(k-2)$ -cell in the boundary of a $(k+1)$ -cell, $1 \leq k \leq d$ , all of the $k$ - and $(k-1)$ -cells 'between them' can be ordered 'around' the $(k-2)$ -cell. This includes the usual orderings in 2- and 3-dimensional objects. We introduce the 'cell-tuple structure', a simple, uniform representation of the incidence and ordering information in a subdivided manifold. It includes the quad-edge data structure of Guibas and Stolfi [GS 85] and the facet-edge data structure of Dobkin and Laszlo [DL 87] as special cases in dimensions 2 and 3, respectively.

¹This work was supported by the National Science Foundation, under grant CCR-8657562, and Digital Equipment Corporation.

Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.

1.2. 1 Introduction

A traditional method of representing geometric objects is as a collection of simple building blocks along with a relation between them. For instance, the building blocks could be simplices or convex polytopes of various dimensions, and the relation could be incidence. One might implement such a description by a separate instance of a data structure for each building block, and a monolithic data structure for the relation. Alternatively, it is possible to use a single type of basic unit, and represent both the building blocks and the relation implicitly. The aim of this paper is to investigate such alternative data structures in the general case of $d \geq 1$ , representing both topological structure and available ordering information in a simple, uniform way.

Subdivided manifolds: Let $M$ be a topological $d$ -manifold, and $C = \{c_\alpha\}_{\alpha \in I_C}$ a finite collection of disjoint open $k$ -cells whose union is $M$ (for $0 \leq k \leq d$ , $c_\alpha$ is an open $k$ -cell if it is homeomorphic to the open unit $k$ -ball). Informally, the pair $(M, C)$ is a subdivided $d$ -manifold if the boundary of every $k$ -cell $c_\alpha \in C$ is non-self-intersecting and is equal to a union of cells in $C$ of lower dimension.

Examples of subdivided manifolds:

The diagram shows two manifolds. On the left is a 2-sphere, represented as a circle with a dashed line indicating its 3D nature. On the right is a Klein bottle, represented as a square grid with labels. The grid is divided into four quadrants labeled A, B, C, and D. The top-left quadrant (A) contains labels 7, A, 3, B, 8. The top-right quadrant (B) contains labels c, 5, d, 6, c. The bottom-left quadrant (C) contains labels b, 1, a, 2, b. The bottom-right quadrant (D) contains labels 8, C, 4, D, 7. The grid is surrounded by arrows indicating its topology.

Diagram showing a 2-sphere and a Klein bottle with their subdivisions.

$M$ is a 2-sphere

$M$ is a Klein bottle

A 3D wireframe diagram of a rectangular prism with a triangular prism attached to its top surface, representing a 3-manifold-with-boundary.

Diagram of a 3-manifold-with-boundary.

$M$ is a 3-manifold-with-boundary

The cell-tuple structure: We will define the cell-tuple structure, which represents a subdivided $d$ -manifold as a set of $(d+1)$ -tuples acted on by simple operators $switch_k$ for $0 \leq k \leq d$ . Theorem I will show that two subdivided manifolds are topologically equivalent if and only if their cell-tuple structures are equivalent. The cell-tuple structure may be thought of as: a set of tuples, acted on by a uniform set of operations following simple algebraic rules; as a graph with labelled edges; or as a triangulation of the underlying manifold. It may be implemented as a relational database or as a pointer structure. Because of its uniformity, one implementation may be written for all values of $d \geq 1$ .

Ordering: Many algorithms in computational geometry have made use of ordering information. Two examples are the three dimensional convex hull algorithm of Preparata and Hong [PR 77], and the Delaunay diagram algorithm of Guibas and Stolfi [GS 85]. Both

give optimal divide-and-conquer algorithms using ordering in 2-dimensional subdivisions. Some examples of ordering:

A 2D diagram showing a triangulation of a polygon. Two vertices are labeled A and B. Arrows indicate the ordering of cells around these vertices.

Diagram illustrating ordering in two dimensions.

In two dimensions

A 3D diagram showing a cube with internal diagonals. Three vertices are labeled A, B, and C. Arrows indicate the ordering of cells around these vertices.

Diagram illustrating ordering in three dimensions.

In three dimensions

In case A, we are ordering 1- and 2-cells about a 0-cell, and in case B we are ordering 0- and 1-cells 'within' a 2-cell. In case C, we are ordering 2- and 3-cells about a 1-cell, in case D we are ordering the 1- and 2-cells within a 3-cell and about a 0-cell, and in case E we are ordering 0- and 1-cells within a 2-cell. All of these cases will be put into one framework, and Theorem II will show that this type of ordering information exists for all $d \geq 1$ .

Manifolds-with-boundary: The objects being modelled in applications often have boundaries. To be useful, any representation of geometric structures must be able to handle objects with boundaries as elegantly and uniformly as those without boundaries. The definition for a subdivision of a manifold-with-boundary is similar to that for the subdivision of a manifold.

The dual subdivision: For every $k$ -cell in $(M, C)$ , a dual $(d-k)$ -cell can be defined, giving the dual subdivision. There is a 1-1 correspondence between the original cells and the dual cells, and incidence and order are preserved when going to the dual. It is often useful to maintain both the original subdivision and its dual simultaneously, and to be able to access both with equal ease. For instance, the Voronoi diagram and Delaunay diagrams are dual to each other, as are the convex hull and halfspace intersection. Producing one implicitly produces the other.

Previous work: Guibas and Stolfi [GS 85] pioneered the idea of such alternatives with the introduction of the ‘quad-edge data structure’ for the representation of subdivisions of 2-manifolds (without boundaries). Dobkin and Laszlo [DL 87] defined an analogous structure, the ‘facet-edge data structure’, to represent subdivisions of 3-manifolds which are homeomorphic to open or closed unit 3-balls. Both the quad-edge and facet-edge data structures represent their subdivisions up to topological equivalence, represent the dual and original subdivisions in a similar fashion, and allow cell boundaries to self-intersect under appropriate restrictions. Note that our definition allows a larger class of manifolds, by allowing arbitrary manifolds with or without boundary, but restricts the class of cells by not allowing self-intersecting cell boundaries.

1.3. 2 The Cell-Tuple Structure

In this section we will define a partial ordering on the set of cells, introduce the switch operator, and define the cell-tuple structure. Then we will state Theorem I, give several characterizations of the cell-tuple structure, and briefly discuss implementation.

We gave an informal definition of subdivided manifolds in the introduction. Using terminology from algebraic topology, a subdivided $d$ -manifold $(M, C)$ is a finite, regular CW complex $C = \{c_\alpha\}_{\alpha \in I_C}$ whose underlying space is the topological $d$ -manifold $M$ . (The reader is referred to [Br 88] for details, and to [Mu 75] and [Mu 84] for definitions of basic topological terms.) If $c_{\alpha_1}$ is contained in the boundary of $c_{\alpha_2}$ we will write $c_{\alpha_1} < c_{\alpha_2}$ , and say that $c_{\alpha_1}$ is a face of $c_{\alpha_2}$ . In addition, $\dim(c_{\alpha_2}) = \dim(c_{\alpha_1}) + 1$ , we will write $c_{\alpha_1} < c_{\alpha_2}$ , and say that $c_{\alpha_1}$ and $c_{\alpha_2}$ are incident. Two subdivided $d$ -manifolds are equivalent if there is a homeomorphism between $M$ and $N$ carrying $k$ -cells onto $k$ -cells. For notational convenience, we assume the existence of a cell $c_{\alpha_{-1}}$ of dimension $-1$ and a cell $c_{\alpha_{d+1}}$ of dimension $d+1$ , such that $c_{\alpha_{-1}} < c_\alpha < c_{\alpha_{d+1}}$ for all $c_\alpha \in C$ . This is notation only; for example, when we write $c_{\alpha_{k-1}} < c_{\alpha_k} < c_{\alpha_{k+1}}$ , where $\dim(c_{\alpha_i}) = i$ , it will be understood that if $k = 0$ , this simply means $c_{\alpha_0} < c_{\alpha_1}$ , and if $k = d$ , it means $c_{\alpha_{d-1}} < c_{\alpha_d}$ .

An important fact, interesting in its own right, is given by the following lemma.

Lemma 1: If $(M, C)$ is a subdivided $d$ -manifold, $c_{\alpha_{k-1}} < c_{\alpha_k} < c_{\alpha_{k+1}}$ , where $0 \leq k \leq d$ , $c_{\alpha_i} \in C$ , and $\dim(c_{\alpha_i}) = i$ , then there is a unique $c_{\alpha'_k} \neq c_{\alpha_k}$ such that $c_{\alpha_{k-1}} < c_{\alpha'_k} < c_{\alpha_{k+1}}$ .

Proof : See Appendix or [Br 88]. ■

Under the conditions of this claim, define the switch operator, $switch(c_{\alpha_{k-1}}, c_{\alpha_k}, c_{\alpha_{k+1}}) = c_{\alpha'_k}$ . For example, in the Klein bottle example, $switch(c_{\alpha_{-1}}, c_\alpha, c_3) = c_d$ , $switch(c_3, c_1, c_A) = c_7$ , and $switch(c_4, c_C, c_{\alpha_2}) = c_D$ .

If $c_{\alpha_0} < \dots < c_{\alpha_d}$ , then the $(d+1)$ -tuple $(c_{\alpha_0}, \dots, c_{\alpha_d})$ will be called a cell-tuple. The set of all cell-tuples formed by cells in $C$ will be denoted by $T_M$ . If $t \in T_M$ is a cell-tuple and $0 \leq k \leq d$ , we denote the $k^{\text{th}}$ component by $t_k$ . If $t = (c_{\alpha_0}, \dots, c_{\alpha_d})$ , define $switch_k(t) = (c_{\alpha_0}, \dots, c_{\alpha_{k-1}}, c_{\alpha'_k}, c_{\alpha_{k+1}}, \dots, c_{\alpha_d})$ , where $c_{\alpha'_k} = switch(c_{\alpha_{k-1}}, c_{\alpha_k}, c_{\alpha_{k+1}})$ . The cell-tuple structure, $T_M = (T_M, \{switch_k\})$ , is simply the set of cell-tuples taken with the $switch_k$ operations, for $0 \leq k \leq d$ . Pictorially, each cell-tuple $t$ can be thought of as a dot in cell $t_d$ , ‘near’ each of the cells $t_0, \dots, t_{d-1}$ . The following figures illustrate this for the 2-sphere example pictured in the introduction:

(M, C)

A diagram of a 2-sphere represented as a planar graph with vertices labeled a, b, c, d, e. The edges are labeled 1 through 6. The faces are labeled A and B. The diagram illustrates the cell-tuple structure (M, C) for a 2-sphere.

Diagram of a manifold T_M represented by dots. A central cell is labeled (a, 6, B). Three edges are labeled sw_0, sw_1, and sw_2, connecting to cells (d, 6, B), (a, 1, B), and (a, 6, A) respectively.

$T_M$ as dots, with $switch_k(t)$ , $t = (a, 6, B)$

Two cell-tuple structures are equivalent if there is a bijection $j : T_M \rightarrow T_N$ which preserves the switch operation, by which we mean $switch_k(j(t)) = j(switch_k(t)) \quad \forall t \in T_M, \quad 0 \leq k \leq d$ . The following theorem shows that the cell-tuple structure represents subdivided manifolds up to equivalence:

Theorem I: If $(M, C)$ and $(N, D)$ are subdivided $d$ -manifolds, then $(M, C)$ and $(N, D)$ are equivalent if and only if $T_M$ and $T_N$ are equivalent.

Proof : See Appendix or [Br 88]. ▀

It is useful to think of $T_M$ as an undirected graph $G_M$ with labelled edges. The vertex set is $T_M$ , and two vertices $t$ and $t'$ are joined by an edge labelled $k$ if $t = switch_k(t')$ (the edges are well-defined, as $switch_k^2(t) = t$ for all $t \in T_M$ ). This allows the use of results from graph theory, and the application of graph algorithms.

Diagram of the graph G_M. Vertices are dots, and edges are labeled with numbers 0, 1, 2. The graph shows a complex network of connections between the cell-tuples of T_M.

$G_M$

If $w = w_1 \dots w_\ell \in \{0, \dots, d\}^*$ , define

$switch_w(t) = \begin{cases} switch_{w_\ell} \dots switch_{w_1}(t) & \text{if } w \neq \lambda, \\ t & \text{if } w = \lambda. \end{cases}$

If $I \subseteq \{0, \dots, d\}$ , define $switch_{I^*}(t) = \{switch_w(t) \mid w \in I^*\}$ , and let $I\text{-orbit}(t)$ be $switch_{I^*}(t)$ . In terms of the graph, $I\text{-orbit}(t)$ is the set of all vertices reachable from $t$ using edges whose labels are in $I$ . Let $k = \{0, \dots, d\} - \{k\}$ . Then $k\text{-orbit}(t) = switch_{\{0, \dots, k-1, k+1, \dots, d\}^*}(t)$ .

If $c_\alpha$ is a $k$ -cell of $C$ , the set of cell-tuples $assoc(c_\alpha) = \{t \in T_M \mid t_k = c_\alpha\}$ will be called the set of associated cell-tuples of $c_\alpha$ . The next lemma describes the basic relationship between cells of $C$ and orbits in $T_M$ :

Lemma 2: There is a 1-1 correspondence between $k$ -cells and $k$ -orbits: if $c_\alpha$ is a $k$ -cell, and $t \in T_M$ such that $t_k = c_\alpha$ , then $assoc(c_\alpha) = switch_{k^*}(t)$ .

Proof : See Appendix or [Br 88]. ▀

Diagram showing examples of assoc sets. Three dashed circles represent assoc(3), assoc(b), and assoc(A), each containing a set of vertices from T_M.

Examples of assoc

The following lemma, interesting in its own right, gives an algebraic characterization of $T_M$ , and will prove useful in connecting $T_M$ to earlier work:

Lemma 3: If $t \in T_M$ and $i \neq j \in \{0, \dots, d\}$ , then:

$(CT0) \quad switch_i(t) \neq t \text{ and } switch_{ij}(t) \neq t,$

$(CT1) \quad switch_{i^2}(t) = t,$

$(CT2) \quad \text{if } j = i \pm 1, \exists m \geq 2 \text{ s.t. } (switch_{ij})^m(t) = t,$

$(CT3) \quad \text{if } j \neq i \pm 1, \text{ then } (switch_{ij})^2(t) = t.$

Proof : See Appendix or [Br 88]. ■

A natural way to implement a data structure for $T_M$ is by creating two $(d+1)$ -vectors for each cell-tuple $t \in T_M$ . The $k^{\text{th}}$ entry in the first vector represents the cell $t_k$ , and the $k^{\text{th}}$ entry in the second vector points to $switch_k(t)$ . The cell-vectors may be thought of as forming a database, allowing relational queries, and graph algorithms may be applied to the pointers in the switch-vectors.

For instance, if $c_\alpha$ is a $k$ -cell, $assoc(c_\alpha)$ may be obtained by a relational query asking for all cell-vectors whose $k^{\text{th}}$ entry is $c_\alpha$ . Alternatively, by choosing a cell-tuple $t$ such that $t_k = c_\alpha$ , a depth-first search of all edges of $G_M$ whose label is not $k$ gives $assoc(c_\alpha)$ in linear time, since $assoc(c_\alpha) = switch_{k^*}(t)$ . Either method gives a way of accessing incidence information.

The set of cells forming the boundary of a cell may be formed in a similar way, by either a relational query or a graph search. If $k > 1$ then the boundary of a $k$ -cell $c_\alpha$ is a $(k-1)$ -subdivided manifold, and a $(k-1)$ -dimensional cell-tuple structure may be created for the boundary by creating $switch_{\{0, \dots, k-1\}}(t)$ , where $t_k = c_\alpha$ , and simply ignoring all but the first $k$ entries of the cell-tuples. Taken in reverse, this gives a natural way of building objects recursively (on dimension) by constructing boundaries of $k$ -cells, associating these boundaries with $k$ -cells, and then attaching these to each other by 'identifying faces' to give a subdivided $k$ -manifold.

Two important issues which will be explored in future work are the size of the cell-tuple structure, and the maintenance of the connection between topological structure and geometric information.

1.4. 3 Order Information in the Topology

The examples of ordering given in the introduction may be put into one framework, and generalized to the general case of $d \geq 1$ . If $c_{\alpha_{k-2}} < c_{\alpha_{k+1}}$ , where $1 \leq k \leq d$ , $c_{\alpha_{k-2}}$ is a $(k-2)$ -cell, and $c_{\alpha_{k+1}}$ is a $(k+1)$ -cell, let

$S(c_{\alpha_{k-2}}, c_{\alpha_{k+1}}) = \{c_\alpha \in C \mid c_{\alpha_{k-2}} < c_\alpha < c_{\alpha_{k+1}}\}.$

It is this set which can be ordered. Note that in the cases that $k = 1$ and $k = d$ , the cells $c_{\alpha_{k-2}} (= c_{\alpha_{-1}})$

and $c_{\alpha_{k+1}} (= c_{\alpha_{d+1}})$ , respectively, are only notational conveniences — only one actual cell is specified, as long as $d > 1$ . In the special case of $d = 1$ , it must be that $k = 1$ , $c_{\alpha_{k-2}} = c_{\alpha_{-1}}$ , and $c_{\alpha_{k+1}} = c_{\alpha_{d+1}}$ ; a circular ordering is possible only if $M$ is connected. This is the only exception which must be treated separately.

Let $m = |S(c_{\alpha_{k-2}}, c_{\alpha_{k+1}})|$ . A circular ordering of $S(c_{\alpha_{k-2}}, c_{\alpha_{k+1}})$ is an ordering $c_{\alpha^0}, \dots, c_{\alpha^{m-1}}$ of its cells such that:

(1) $c_{\alpha^i}$ is a $(k-1)$ -cell if $i$ is even, and is a $k$ -cell if $i$ is odd,
(2) $c_{\alpha^i}$ and $c_{\alpha^{i+1 \bmod m}}$ are incident for $0 \leq i \leq m-1$ .

(A more descriptive way of stating condition (2) is to say that $c_{\alpha^{i-1 \bmod m}}$ and $c_{\alpha^{i+1 \bmod m}}$ 'share' $c_{\alpha^i}$ .)

The idea is that given a $(k-2)$ -cell contained in the boundary of a $(k+1)$ -cell, all of the cells 'between' them may be put into a circular order 'around' the $(k-2)$ -cell. This order alternates between $(k-1)$ -cells and $k$ -cells so that two cells are consecutive in the ordering if and only if they are incident. Recalling the Klein bottle example, one possible circular ordering of $S(c_\alpha, c_\beta)$ is $c_2, c_B, c_3, c_A, c_1, c_C, c_4, c_D$ . The reason this idea is not more obvious when trying to generalize from two and three dimensions is that of the five cases, namely $d = 2, k = 1, 2$ and $d = 3, k = 1, 2, 3$ , only one case specifies two cells; in the other four, either $k = 1$ or $k = d$ . Theorem II shows that circular orderings involving $(k-1)$ - and $k$ -cells are always present for $1 \leq k \leq d$ , and that the cell-tuple structure contains this ordering information in a directly accessible form via the switch operator.

Theorem II: Under the conditions given above there exists a circular ordering of $S(c_{\alpha_{k-2}}, c_{\alpha_{k+1}})$ . Furthermore, if $t^0 \in T_M$ such that $t_{k-2}^0 = c_{\alpha_{k-2}}$ and $t_{k+1}^0 = c_{\alpha_{k+1}}$ , define

$t^i = \begin{cases} switch_k(t^{i-1}) & i \text{ even,} \\ switch_{k-1}(t^{i-1}) & i \text{ odd.} \end{cases}$

Then $t_{k-1}^0, t_k^1, t_{k-1}^2, t_k^3, \dots, t_{k-1}^{m-2}, t_k^{m-1}$ is a circular ordering of $S(c_{\alpha_{k-2}}, c_{\alpha_{k+1}})$ .

Proof : See Appendix or [Br 88]. ■

This gives a straightforward way of accessing order information by alternating applications of switch_k and switch_k-1.

1.5. 4 Extensions

1.5.1. 4.1 Manifolds-with-Boundary

In generalizing the cell-tuple structure from manifolds to manifolds-with-boundary, the problem is that $switch(c_{\alpha_{d-1}}, c_{\alpha_d}, c_{\alpha_{d+1}})$ is not defined when $c_{\alpha_{d-1}} \subseteq \partial M$ . Stated in terms of cell-tuples, $switch_d(t)$ is not defined if $t_{d-1} \in \partial M$ .

There are two possible approaches. The first is to set $switch$ to some special value in the undefined cases, indicating that an attempt was made to 'pierce the boundary.' Then the definition of circular ordering may be modified so that when $k = d$ and $c_{\alpha_{k-2}} \subseteq \partial M$ , the ordering is a simple path rather than a simple cycle. The theorems may then be proved as before.

The second approach may be described intuitively as imagining that the space 'outside' of the $d$ -manifold-with-boundary is simply another $d$ -cell (though in general, the complement of a $d$ -manifold-with-boundary embedded in $\mathbb{R}^n$ is not a $d$ -cell). An abstract object $c_{\alpha_\infty}$ is added to $C$ , such that for every $c_\alpha$ contained in $\partial M$ , $c_\alpha < c_{\alpha_\infty}$ . Now $switch$ may be defined as before on the set $C \cup \{c_{\alpha_\infty}\}$ , and all of the results for subdivided manifolds can be proved for subdivided manifolds-with-boundary (see [Br 88] for details). In addition, this makes it possible to find the 'next' cell on the boundary. An example of circular ordering at the boundary:

The diagram shows two approaches to handling manifolds-with-boundary. The first approach shows a V-shaped region with cells $c_{\alpha^0}, c_{\alpha^1}, c_{\alpha^2}, c_{\alpha^3}, c_{\alpha^4}$ and cell-tuples $sw_1, sw_2$ . The second approach adds a cell $c_{\alpha^5} = c_{\alpha_\infty}$ to the first approach, showing a similar V-shaped region with an additional cell $c_{\alpha^5}$ and cell-tuples $sw_1, sw_2$ .

Diagrams illustrating two approaches to handling manifolds-with-boundary. The first approach shows a V-shaped region with cells c_alpha^0, c_alpha^1, c_alpha^2, c_alpha^3, c_alpha^4 and cell-tuples sw_1, sw_2. The second approach adds a cell c_alpha^5 = c_alpha_infinity to the first approach, showing a similar V-shaped region with an additional cell c_alpha^5 and cell-tuples sw_1, sw_2.

1.5.2. 4.2 The Dual Complex

For every $k$ -cell in $(M, C)$ , a dual $(d-k)$ -cell can be easily defined (see [Br 88]). There is a 1-1 correspondence between original cells and dual cells, and incidence and order are preserved when going between the original and the dual. The cell-tuple structure maintains both the original and dual complexes simultaneously. To operate in the dual, note that $switch_k$ in the original subdivided manifold is the same thing as $switch_{d-k}$ in the dual. Thus the same ordering results apply in the dual, by replacing $k$ with $d-k$ , and one way to think of operating on the dual is to think of substituting $switch_{d-k}$ for every use of $switch_k$ .

An alternative, which will make the connection with earlier work straightforward, is to introduce a new operation which reverses the order of a cell-tuple's entries, $switch_R(c_{\alpha_0}, \dots, c_{\alpha_d}) = (c_{\alpha_d}, \dots, c_{\alpha_0})$ , and define $T_M^{dual} = \{switch_R(t) \mid t \in T_M\}$ . Thus $switch_R$ maps $T_M$ onto $T_M^{dual}$ and vice versa.

The diagram illustrates the $switch_R$ operation. It shows a V-shaped region with cells $c_{\alpha^0}, c_{\alpha^1}, c_{\alpha^2}, c_{\alpha^3}, c_{\alpha^4}$ and cell-tuples $sw_1, sw_2$ . The diagram shows the original cell-tuple $(1, 4)$ and the dual cell-tuple $(d, 4, A)$ after applying $switch_R$ .

Diagram illustrating the switch_R operation. It shows a V-shaped region with cells c_alpha^0, c_alpha^1, c_alpha^2, c_alpha^3, c_alpha^4 and cell-tuples sw_1, sw_2. The diagram shows the original cell-tuple (1, 4) and the dual cell-tuple (d, 4, A) after applying switch_R.

Examples of $switch_R$

Consider the set of tuples $T_M \cup T_M^{dual}$ , acted on by $switch_R$ and $switch_k, 0 \leq k \leq d$ . A new property may be added to (CT0) – (CT3) of Lemma 3:

(CT4) $switch_{RiR}(t) = switch_{d-i}(t)$ .

1.5.3. 4.3 The Augmented Incidence Poset

If $(M, C)$ is a subdivided manifold, the relation $<$ is a strict partial ordering on $C$ . The resulting partially ordered set $(C, <)$ represents the topology of $(M, C)$ ; a theorem analogous to Theorem I may be proved. This is essentially the same thing as the familiar incidence graph. By adding the $switch$ operation, all ordering information becomes directly accessible — given $c_{\alpha_{k-2}} < c_{\alpha_{k+1}}$ , a circular ordering is obtained by applying a sequence of $switch$ operations: if $c_{\alpha_{k-2}} < c_{\alpha^0} < c_{\alpha^1} < c_{\alpha_{k+1}}$ and $2 \leq i \leq m-1$ then

$c_{\alpha^i} = \begin{cases} switch(c_{\alpha_{k-2}}, c_{\alpha^{i-2}}, c_{\alpha^{i-1}}) & i \text{ even,} \\ switch(c_{\alpha^{i-1}}, c_{\alpha^{i-2}}, c_{\alpha_{k+1}}) & i \text{ odd,} \end{cases}$

gives a circular ordering $c_{\alpha^0}, \dots, c_{\alpha^{m-1}}$ of $S(c_{\alpha^{h-2}}, c_{\alpha^{h+1}})$ . Such $c_{\alpha^0}$ and $c_{\alpha^1}$ always exist.

Any data structure for representing graphs will suffice to represent the incidence poset. The $switch_k$ operator may be represented for any subset of $\{0, \dots, d\}$ ; for a given $k$ , this means representing a function whose domain is the set of all cell-triples $c_{\alpha^{h-1}} \prec c_{\alpha^h} \prec c_{\alpha^{h+1}}$ and whose range is the set of $k$ -cells. This may be an advantage if ordering information is needed in only a small number of dimensions. If $switch_k$ is included for all $0 \leq k \leq d$ , the resulting augmented incidence poset contains all of the ordering information via the switch operations.

1.6. 5 Relation to Earlier Work

1.6.1. 5.1 The Quad-Edge Data Structure

Guibas and Stolfi [GS 85] introduced the quad-edge data structure for the representation of subdivided 2-manifolds (without boundaries), in which cell boundaries are allowed to self-intersect under appropriate restrictions. Subdivisions are represented up to equivalence, and the dual subdivision is represented in a symmetric fashion to that of the original subdivision. Four ‘directed, oriented edges’ are produced for each edge in the original and dual subdivisions, corresponding to the four ways of giving direction and orientation to the edge. We will draw a directed, oriented edge as a large arrow giving the direction, with a small arrow sticking from its side giving the orientation (which direction ‘to rotate in’). There are three operations defined on directed, oriented edges: Flip reverses the orientation, Rot essentially rotates about the midpoint by 90 degrees (into the dual), and Next gives the next directed, oriented edge encountered when rotating about the larger arrow’s base. These operations satisfy ten algebraic rules.

Diagram illustrating the Quad-Edge Data Structure. It shows two sets of edges. The left set shows four directed, oriented edges (large arrows with small side arrows) meeting at a central point, representing the four ways to give direction and orientation to an edge. The right set shows three operations: Flip (reversing orientation), Rot (rotating 90 degrees), and Next (rotating around the base of the larger arrow).

Eight directed, oriented edges

Examples of Flip, Rot, and Next

Diagram illustrating the corresponding section of G_M. It shows a graph with nodes and edges, where some edges are solid and some are dashed, representing the original and dual subdivisions. The edges are labeled with numbers 1, 2, and 3, indicating specific edges in the structure.

Corresponding section of $G_M$

There is a 1-1 correspondence between directed, oriented edges in the quad-edge data structure and cell-tuples in $T_M \cup T_M^{dual}$ . A cell-tuple $t \in T_M$ represents a directed, oriented original edge: $t_1$ gives the edge, $t_0$ gives the direction (as the base of the larger arrow), and $t_2$ gives the orientation (which face the little arrow points into). Similarly, if $t \in T_M^{dual}$ , $t$ represents a directed, oriented dual edge, by taking the duals of $t_0, t_1$ and $t_2$ . The connection between the operations in the two structures is given by: $Next = switch_{12}$ , $Flip = switch_2$ , $Rot = switch_{2R}$ . To show that the quad-edge data structure and $T_M$ are equivalent on the structures for which they are both defined (subdivided 2-manifolds as defined in this paper) means showing that the properties (CT0) – (CT4) hold if and only if the ten rules for quad-edge operations hold. It is interesting to note that the explicit inclusion of dual elements is not necessary in the quad-edge data structure for representational power. Using only directed, oriented original edges, and the operations Next, Flip and Sym ( $Sym = Rot^2$ can be written as $Sym = switch_{01}$ ) gives a structure equivalent to $T_M$ .

1.6.2. 5.2 The Facet-Edge Data Structure

Dobkin and Laszlo [DL 87] created the facet-edge data structure to represent subdivided 3-manifolds, which is analogous to the quad-edge data structure. For every (face, edge) pair such that the face and edge are incident, there are four ‘facet-edges’, corresponding to the ways of defining ‘clockwise’ directions within the face, and around the edge. Similar basic units are created for pairs in the dual. An original facet-edge may be represented by a cell-tuple as follows: $t_1$ gives the edge, $t_2$ gives the face, $t_0$ gives the direction within the face, and $t_3$ gives the direction around the edge. A similar representation holds for dual pairs and dual cell-tuples. The basic operations can be rewritten in terms of the switch operations: $Clock = switch_{03}$ , $Enext = switch_{01}$ , $Fnext = switch_{32}$ , $Rev = switch_3$ , $Sdual = switch_R$ . The underlying spaces are 3-manifolds which are homeomorphic to open or closed unit 3-balls, and cell boundaries are allowed to self-intersect under appropriate restrictions.

Acknowledgement: I would like to thank my advisor, Richard Anderson, for introducing me to [GS 85] and for his continuing help, support, and encouragement.

1.7. Appendix – Proofs

In this appendix we will give proof sketches for the lemmas and theorems.

Define an order relation on the index sets to agree with $<$ on cells: If $\alpha_1, \alpha_2 \in I_C$ , then $\alpha_1 < \alpha_2 \Leftrightarrow c_{\alpha_1} < c_{\alpha_2}$ . Also, let $\dim(\alpha) = \dim(c_\alpha)$ . Let $\mathcal{P}_M = (I_C, <)$ denote the resulting incidence poset on indices. Two such posets $\mathcal{P}_M$ and $\mathcal{P}_N$ are equivalent if there exists a bijection between their index sets preserving $<$ and $\dim$ . We briefly describe a method of triangulating a subdivided manifold, such that there is a 1-1 correspondence between cell-tuples and $d$ -simplices. This allows the use of theorems from algebraic topology which apply to triangulated manifolds, when proving properties of $\mathcal{T}_M$ . If $(M, C)$ is a subdivided $d$ -manifold or a subdivided manifold-with-boundary, define $\mathcal{A}_M = \{\{\alpha_{i_0}, \dots, \alpha_{i_\ell}\} \mid \alpha_{i_0} < \dots < \alpha_{i_\ell}, \ell \geq 0\}$ . $\mathcal{A}_M$ is an abstract simplicial complex. Two such abstract simplicial complexes $\mathcal{A}_M$ and $\mathcal{A}_N$ are equivalent if there exists a bijection between their vertex sets which preserves $\dim$ and simplices. Let $K_M$ be any geometric realization of $\mathcal{A}_M$ (which always exists by [Mu 84] Theorem 3.1.a), and let $|K_M| = \bigcup_{\sigma \in K_M} \sigma$ be its underlying space. For each $\alpha \in I_C$ , let $v_\alpha$ be the corresponding vertex in $K_M$ , and define $label(v_\alpha) = \dim(\alpha)$ . Let $\sigma(\alpha_{i_0}, \dots, \alpha_{i_\ell})$ be the $\ell$ -simplex defined by $v_{\alpha_{i_0}}, \dots, v_{\alpha_{i_\ell}}$ . $K_M$ and $K_N$ are equivalent if there exists a linear simplicial map $f : |K_M| \rightarrow |K_N|$ which is bijective and preserves label. The following lemma makes an important connection between any such $K_M$ and $(M, C)$ :

Lemma 4: If $(M, C)$ is a subdivided $d$ -manifold

or a subdivided $d$ -manifold-with-boundary, then $\exists \psi_M : |K_M| \rightarrow M$ such that:

(a) $\psi_M$ is a homeomorphism,
(b) $c_\alpha = \bigcup_{\alpha_0 < \dots < \alpha_\ell < \alpha} cs(\alpha_0, \dots, \alpha_\ell, \alpha)$ ,

where $cs(\alpha_{i_0}, \dots, \alpha_{i_\ell}) = \psi_M(\text{Int } \sigma(\alpha_{i_0}, \dots, \alpha_{i_\ell}))$ , and the set of sequences over which the union is taken includes the sequence consisting only of $\alpha$ .

Proof : A construction of such a $\psi_M$ is given in the proof sketch of [LW 69] Theorem III.1.7. A construction is also given in [Br 88]. ■

Let $C_{sd} = \{cs(\alpha_{i_0}, \dots, \alpha_{i_\ell}) \mid (\alpha_{i_0}, \dots, \alpha_{i_\ell}) \in K_M\}$ . $(M, C_{sd})$ is a subdivided manifold itself, which will be called the generalized barycentric subdivision of $(M, C)$ . (Note that this generalization is different than that given in [Mu 84], and that the generalized barycentric subdivision in two dimensions is called the ‘completion’ in [GS 85].) Because the characteristic maps which define $C$ are not part of the definition of subdivided $d$ -manifolds, the barycentric subdivision is not unique, but is unique up to equivalence.

By their definitions, there is a 1-1 correspondence between the cell-tuples in $\mathcal{T}_M$ and the $d$ -simplices in $K_M$ : $(c_{\alpha_0}, \dots, c_{\alpha_d})$ corresponds to $\sigma(\alpha_0, \dots, \alpha_d)$ . Furthermore, if $t, t' \in \mathcal{T}_M$ , and $\sigma, \sigma'$ are the corresponding $d$ -simplices in $K_M$ , then $t' = switch_k(t) \Leftrightarrow \sigma' \cap \sigma$ is a $(d-1)$ -simplex labelled by $\hat{k}$ . Using this, and [Mu 84] exercise 35.4, it is easy to prove that if $c_{\alpha_{i_0}} < \dots < c_{\alpha_{i_\ell}}$ , then there exists a $t \in \mathcal{T}_M$ such that $t_{i_j} = c_{\alpha_{i_j}}$ , $0 \leq j \leq \ell$ . Lemma 1 follows from this correspondence, the definition of cell-tuples, and [Mu 84] exercise 35.4.

We can now sketch the proof for a generalization of Lemma 2. First generalize the definition of assoc: If $c_{\alpha_{i_0}} < \dots < c_{\alpha_{i_\ell}}$ , then $assoc(c_{\alpha_{i_0}}, \dots, c_{\alpha_{i_\ell}}) = \{t \in \mathcal{T}_M \mid t_{i_j} = c_{\alpha_{i_j}}, 0 \leq j \leq \ell\}$ . If $I \subseteq \{0, \dots, d\}$ , let $\hat{I} = \{0, \dots, d\} - I$ .

Lemma 2': If $c_{\alpha_{i_0}} < \dots < c_{\alpha_{i_\ell}}$ , and $t \in \mathcal{T}_M$ such that $t_{i_j} = c_{\alpha_{i_j}}$ , $0 \leq j \leq \ell$ , then $assoc(c_{\alpha_{i_0}}, \dots, c_{\alpha_{i_\ell}}) = switch_{\hat{I}}(t)$ , where $I = \{i_0, \dots, i_\ell\}$ .

Proof (sketch) : To see that $switch_{\hat{I}}(t) \subseteq assoc(c_{\alpha_{i_0}}, \dots, c_{\alpha_{i_\ell}})$ is easy: If $k \in \hat{I}$ , then $switch_k t$ doesn't change $t_j$ for any $j \in I$ . So if $t' = switch_w(t)$ , for any $w \in \hat{I}^*$ , then $t'_j = t_j$ for all $j \in I$ , i.e. $t' \in \text{assoc}(c_{\alpha_{i_0}}, \dots, c_{\alpha_{i_l}})$ .

That $\text{assoc}(c_{\alpha_{i_0}}, \dots, c_{\alpha_{i_l}}) \subseteq \text{switch}_{j_k}(t)$ follows from this claim: If $c_{\alpha_{i_0}} < \dots < c_{\alpha_{i_l}}$ , where $c_{\alpha_{i_k}} \in C$ , and $I = \{i_0, \dots, i_l\}$ , then the subgraph of $G_M$ induced by $\text{assoc}(c_{\alpha_{i_0}}, \dots, c_{\alpha_{i_l}})$ is connected and its edges are all labelled by elements of $\hat{I}$ . This claim is proved by first showing that $[Star \sigma(\alpha_{i_0}, \dots, \alpha_{i_l})]$ in $K_M$ is a compact triangulated relative homology $d$ -manifold. Then connectivity follows from [Mu 84] Corollary 70.3 and the correspondence between cell-tuples and $d$ -simplices. If $t, t' \in \text{assoc}(c_{\alpha_{i_0}}, \dots, c_{\alpha_{i_l}})$ , then they agree on all components in $I$ , so that if $t' = \text{switch}_k(t)$ , then $k \in \hat{I}$ . This gives the claim. Details in [Br 88]. ■

Now we can prove Lemma 3.

Lemma 3: If $t \in T_M$ and $i \neq j \in \{0, \dots, d\}$ , then:

(CT0) $\text{switch}_i(t) \neq t$ and $\text{switch}_{ij}(t) \neq t$ ,
(CT1) $\text{switch}_{i2}(t) = t$ ,
(CT2) if $j = i \pm 1$ , $\exists m \geq 2$ s.t. $(\text{switch}_{ij})^m(t) = t$ ,
(CT3) if $j \neq i \pm 1$ , then $(\text{switch}_{ij})^2(t) = t$ .

Proof : CT0 and CT1 follow from Lemma 1 and the definition of switch.

Let $t \in T_M$ , and $I = \{0, \dots, d\} - \{i, j\}$ . Let $c_{\alpha_{i_k}} = t_{i_k}$ for $i_k \in I$ , so that $\{c_{\alpha_{i_0}}, \dots, c_{\alpha_{i_{d-2}}}\} = \{t_k \mid k \in I\}$ . The subgraph of $G_M$ induced by $\text{assoc}(c_{\alpha_{i_0}}, \dots, c_{\alpha_{i_{d-2}}})$ is connected, by Lemma 2'. Since every vertex is incident to exactly one edge labelled $i$ and one labelled $j$ , this subgraph is a cycle, with alternating edges labelled $i$ and $j$ . If $j = i \pm 1$ , this gives CT2. If $j \neq i \pm 1$ , then there are exactly two $i$ -cells $c_{\alpha_i}, c_{\alpha_{i'}}$ , satisfying $t_{i-1} \prec c_{\alpha_i} \prec t_{i+1}$ and there are exactly two $j$ -cells $c_{\alpha_j}, c_{\alpha_{j'}}$ , satisfying $t_{j-1} \prec c_{\alpha_j} \prec t_{j+1}$ . Thus $\text{assoc}(c_{\alpha_{i_0}}, \dots, c_{\alpha_{i_{d-2}}})$ has exactly four elements. This gives CT3. ■

We give a generalization of Theorem I, which shows that both the cell-tuple structure and the incidence poset are powerful enough to represent subdivided manifolds up to equivalence. For each of the structures discussed, the symbol $\simeq$ means 'is equivalent'.

Theorem I': If $(M, C)$ and $(N, D)$ are subdivided $d$ -manifolds, then the following are equivalent:

(1) $(M, C) \simeq (N, D)$ ,
(2) $\mathcal{P}_M \simeq \mathcal{P}_N$ ,
(3) $T_M \simeq T_N$ .

Proof (sketch) :

$(M, C) \simeq (N, D) \Rightarrow \mathcal{P}_M \simeq \mathcal{P}_N$ : Let $h : M \rightarrow N$ give an equivalence between $(M, C)$ and $(N, D)$ . Define an equivalence $\iota : I_C \rightarrow I_D$ by $\iota(\alpha) = \text{index}(h(c_\alpha))$ .

$\mathcal{P}_M \simeq \mathcal{P}_N \Rightarrow K_M \simeq K_N$ : Let $\iota : I_C \rightarrow I_D$ give an equivalence between $\mathcal{P}_M$ and $\mathcal{P}_N$ . First show that $\iota$ preserves simplices, hence gives an equivalence between $\mathcal{A}_M$ and $\mathcal{A}_N$ . The result then follows from [Mu 84] Theorem 3.1.b, when it is noted that the isomorphism produced there preserves labels.

$K_M \simeq K_N \Rightarrow (M, C) \simeq (N, D)$ : Let $f : |K_M| \rightarrow |K_N|$ give an equivalence between $|K_M|$ and $|K_N|$ . Let $\psi_M : |K_M| \rightarrow M$ and $\psi_N : |K_N| \rightarrow N$ be maps giving generalized barycentric subdivisions. These exist by Lemma 4. Define $h : M \rightarrow N$ by $h = \psi_N \circ f \circ \psi_M^{-1}$ . This is a composition of homeomorphisms, so is a homeomorphism. Now show that $h$ takes $k$ -cells onto $k$ -cells, using Lemma 4, the definition of $h$ , and the fact that $f$ is an equivalence.

$\mathcal{P}_M \simeq \mathcal{P}_N \Rightarrow T_M \simeq T_N$ : Let $\iota : I_C \rightarrow I_D$ be an equivalence between $\mathcal{P}_M$ and $\mathcal{P}_N$ . Define $j : T_M \rightarrow T_N$ by $j((c_{\alpha_0}, \dots, c_{\alpha_d})) = (d_{i_1(\alpha_0)}, \dots, d_{i_d(\alpha_d)})$ . The desired properties follow from the 1-1 correspondence between maximal paths in $\mathcal{P}_M$ and cell-tuples in $T_M$ , and the fact that $t' = \text{switch}_k(t)$ if and only if $t$ and $t'$ agree on all components except the $k^{\text{th}}$ .

$T_M \simeq T_N \Rightarrow \mathcal{P}_M \simeq \mathcal{P}_N$ : Let $j : T_M \rightarrow T_N$ give an equivalence between $T_M$ and $T_N$ . Define $\iota : I_C \rightarrow I_D$ by $\iota(\alpha) = \text{index}(\text{assoc}^{-1}(j(\text{assoc}(c_\alpha))))$ . If $c_\alpha$ is a $k$ -cell, and $t \in T_M$ such that $t_k = c_\alpha$ , then $j(\text{assoc}(c_\alpha)) = j(\text{switch}_{i_k}(t)) = \text{switch}_{i_k}(j(t)) = \text{assoc}(d_\beta)$ for a unique $k$ -cell $d_\beta \in D$ . This, and the fact that $\text{assoc}$ (as a function from $I_C$ to $2^{T_M}$ ) is bijective with its range, gives $\iota(\alpha) = \text{index}(\text{assoc}^{-1}(\text{assoc}(d_\beta))) = \beta$ , so $\iota$ is well-defined and preserves dim. $\iota$ is bijective, since $\text{assoc}$ is bijective with its range, and $\text{index}$ and $j$ are bijective. To show that $\iota$ preserves order, use these two facts: $\text{assoc}(d_\beta) = j(\text{assoc}(c_\alpha))$ ; and $\alpha_1 < \alpha_2 \Leftrightarrow \dim(\alpha_1) < \dim(\alpha_2)$ and $\text{assoc}(c_{\alpha_1}) \cap \text{assoc}(c_{\alpha_2}) \neq \emptyset$ .

See [Br 88] for details. ■

Finally, Theorem II follows from Lemma 2' in the same way that property (CT2) of Lemma 3 did.

1.8. References

[Br 88] Brisson, Erik, "Representing Geometric Structures in $d$ Dimensions: Topology and Order," Tech. Report 88-11-07, Dept. of Computer Science, Univ. of Washington, 1988.
[DL 87] Dobkin, David P. and Laszlo, Michael J., "Primitives for the Manipulation of Three-Dimensional Subdivisions," Proc. 3rd ACM Symp. on Comp. Geometry, 1987. pp. 86-99.
[GS 85] Guibas, Leonidas and Stolfi, Jorge, "Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams," ACM Trans. Graphics, Vol. 4, No. 2, 1985. pp. 74-123.
[LW 69] Lundell, Albert T. and Weingram, Stephen, The Topology of CW Complexes, Van Nostrand Reinhold, 1969.
[Mu 75] Munkres, James R., Topology: A First Course, Prentice-Hall, 1975.
[Mu 84] Munkres, James R., Elements of Algebraic Topology, Addison-Wesley, 1984.
[PR 77] Preparata, F. P. and Hong, S. J., "Convex Hulls of Finite Sets of Points in Two and Three Dimensions," Comm. of the ACM, Vol. 20, No. 2, 1977. pp. 87-93.