Discrete Manifolds: The Graph-Based Theory

This chapter presents a general-purpose definition of discrete curves, surfaces, and manifolds. This definition only refers to a simple graph, \(G=(V,E)\) and its topological structure. Similar to digital manifolds defined in Chap. 5, the ideas presented in this chapter still use recursive definitions for discrete curves, surfaces, solid objects, and so on. Specifically, a vertex is a point-cell, and an edge is a line-cell. A surface-cell (2-cell) is defined as a special simple closed “curve”—a closed semi-curve with the minimum cycle property. In general, a k-cell will be a closed semi \((k-1)\)-manifold with minimum “cycle” property. For a graph G, all i-cells, \(i=0,...,n+1\), will provide topological structure to the discrete space G. An n dimensional discrete manifold M is defined as: (1) M consists of n-cells and any two n-cells are \((n-1)\)-dimensionally connected, (2) each \((n-1)\)-cell in M is contained by one or two n-cells, and (3) there is no \((n+1)\)-cell in M. We also consider the definition of orientable and non-orientable surfaces with a corresponding decision procedure. Finally, some unconventional examples of the definitions, such as quadtree surface-cell representation, an octree solid-cell representation, Voronoi decomposition, and Delaunay simplifications are presented.