Back to search

University of Washington

Representation of d-dimensional geometric objects

Abstract

dc:description.abstract

This work investigates data structures and algorithms for representing and manipulating d-dimensional geometric objects for arbitrary d $\le$ 1. These objects are often described by a set of basic building blocks, together with an incidence relation among the blocks. We give a new representation of such objects, the 'cell-tuple structure', which provides direct access to topological structure, ordering information among cells, the topological dual, and boundaries.We define 'subdivided d-manifolds', a class of geometric objects which is large enough to encompass most computational geometry applications. Our first main result is that both the incidence graph and the cell-tuple structure are powerful enough to represent subdivided d-manifolds up to topological equivalence. Our second main result is that circular orderings of cells exist in subdivided d-manifolds for all 0 $\le$ k $\le$ d: given a (k $-$ 2)-dimensional cell which is incident to a (k + 1)-dimensional cell, there is a simple closed path encountering each of the cells between them exactly once.Our work generalizes the work of Guibas and Stolfi (the quad-edge data structure, representing subdivision of 2-manifolds) and the work of Dobkin and Laszlo (the facet-edge data structure, representing subdivisions of 3-manifolds).The cell-tuple structure gives a simple, uniform representation of subdivided manifolds which unifies the existing work in the field and provides intuitive clarity in all dimensions. In two and three dimensions it is competitive in terms of size and speed with other methods.Operators are defined for accessing structure and ordering information. Structure and ordering within the dual of a subdivided manifold may be accessed in a symmetric manner. Constructors are defined for creating and manipulating subdivided manifolds. Implementation issues are discussed, and an actual implementation is described.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Brisson, Erik, 1957-

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Copyright is held by the individual authors.
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Other
b25766636
24224203

Chain of custody

source
Harvested from
University of Washington
Base URL
digital.lib.washington.edu/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Brisson, Erik, 1957-. Representation of d-dimensional geometric objects. 1990. http://hdl.handle.net/1773/6903