This paper presents a general-purpose definition for discrete curves, surfaces, and manifolds. We also focus on their tracking algorithms and implementations. This definition only refers to a simple graph, G equals (V,E), which is a generalized discrete space. The idea presented in this paper is to recursively define discrete curves, surfaces, solid objects and so forth. Obviously, a vertex is a point- unit-cell, and an edge is a line-unit-cell. A surface-unit- cell is a simple; closed path C if there is no pure subset of C can be a cycle. Based on this intuitive idea, n-D unit- cells can be defined in G for n > 2. For a graph G, i-D unit-cells, i equals 0,..., n + 1, provide a topological structure to the discrete space G. A n-D discrete manifold M is defined as (1) M consists of n-D unit-cells and any two n-D unit-cells are (n - 1)-D connected, (2) each (n - 1)-D unit-cell in M is contained by one or two n-D unit- cells, and (3) there is no (n + 1)-D unit-cell in M. This definition extends a definition extends a definition of digital manifolds. We have developed an linear time algorithm to decide if a subset is a discrete n-D manifold, a linear time algorithm to obtain the k-D boundary for n-D manifold. Such algorithms have been implemented in (Sigma) ₃, a space containing all integer points. This paper also discusses the non-orientable surface, quadtree surface-unit- cell representation, and an octree solid-unit-cell representation.

Date Published: 20 October 1997
PDF: 12 pages
Proc. SPIE 3168, Vision Geometry VI, (20 October 1997); doi: 10.1117/12.292780

Published in SPIE Proceedings Vol. 3168:
Vision Geometry VI
Robert A. Melter; Angela Y. Wu; Longin Jan Latecki, Editor(s)