Representing geometric structures in d dimensions: topology and order

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Representing geometric structures in d dimensions: topology and order

Full text

Pdf (885 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the fifth annual symposium on Computational geometry table of contents

Saarbruchen, West Germany

Pages: 218 - 227

Year of Publication: 1989

ISBN:0-89791-318-3

Author

E. Brisson

Department of Computer Science, University of Washington, Seattle, Washington

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 33, Citation Count: 21

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/73833.73858 What is a DOI?

ABSTRACT

We develop a representation for the topological structure of subdivided manifolds (with and without boundary) of dimension d ≥ 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 ≤ k ≤ 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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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	D. P. Dobkin , M. J. Laszlo, Primitives for the manipulation of three-dimensional subdivisions, Proceedings of the third annual symposium on Computational geometry, p.86-99, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41967]
	GS 85	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	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	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]

CITED BY 21

	Henning Østergård Hansen , Niels Jørgen Christensen, A model for n-dimensional boundary topology, Proceedings on the second ACM symposium on Solid modeling and applications, p.65-73, May 19-21, 1993, Montreal, Quebec, Canada
	F. Bernardini , V. Ferrucci , A. Paoluzzi , V. Pascucci, Product operator on cell complexes, Proceedings on the second ACM symposium on Solid modeling and applications, p.43-52, May 19-21, 1993, Montreal, Quebec, Canada
	Sang Hun Lee , Kunwoo Lee, Partial entity structure: a compact non-manifold boundary representation based on partial topological entities, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.159-170, May 2001, Ann Arbor, Michigan, United States
	Hervé Brönnimann, Degenerate convex hulls on-line in any fixed dimension, Proceedings of the fourteenth annual symposium on Computational geometry, p.249-258, June 07-10, 1998, Minneapolis, Minnesota, United States
	Maged S. Tawfik, An efficient algorithm for CSG to b-rep conversion, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.99-108, June 05-07, 1991, Austin, Texas, United States
	Timothy M. Y. Chan , Jack Snoeyink , Chee-Keng Yap, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.282-291, January 22-24, 1995, San Francisco, California, United States
	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991
	Yasushi Yamaguchi , Fumihiko Kimura, Nonmanifold Topology Based on Coupling Entities, IEEE Computer Graphics and Applications, v.15 n.1, p.42-50, January 1995
	Leila De Floriani , Mostefa M. Mesmoudi , Franco Morando , Enrico Puppo, Decomposing non-manifold objects in arbitrary dimensions, Graphical Models, v.65 n.1-3, p.2-22, January 2003
	Leila De Floriani , Annie Hui, A scalable data structure for three-dimensional non-manifold objects, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Michael J. Laszlo, Techniques for visualizing 3-dimensional manifolds, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
	Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, Proceedings of the 1992 workshop on Volume visualization, p.75-82, October 19-20, 1992, Boston, Massachusetts, United States
	David Cardoze , Alexandre Cunha , Gary L. Miller , Todd Phillips , Noel Walkington, A bézier-based approach to unstructured moving meshes, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Marcelo Kallmann , Daniel Thalmann, Star-vertices: a compact representation for planar meshes with adjacency information, Journal of Graphics Tools, v.6 n.1, p.7-18, September 2001
	Aristides A. G. Requicha , Jarek R. Rossignac, Solid Modeling and Beyond, IEEE Computer Graphics and Applications, v.12 n.5, p.31-44, September 1992
	Leila De Floriani , David Greenfieldboyce , Annie Hui, A data structure for non-manifold simplicial d-complexes, Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, July 08-10, 2004, Nice, France
	A. Paoluzzi , F. Bernardini , C. Cattani , V. Ferrucci, Dimension-independent modeling with simplicial complexes, ACM Transactions on Graphics (TOG), v.12 n.1, p.56-102, Jan. 1993
	Michael T. Goodrich, Applying parallel processing techniques to classification problems in constructive solid geometry, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.118-128, January 22-24, 1990, San Francisco, California, United States
	Leila De Floriani , Annie Hui, Update operations on 3D simplicial decompositions of non-manifold objects, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	S. Horna , D. Meneveaux , G. Damiand , Y. Bertrand, Consistency constraints and 3D building reconstruction, Computer-Aided Design, v.41 n.1, p.13-27, January, 2009
	Leila De Floriani , Annie Hui, Data structures for simplicial complexes: an analysis and a comparison, Proceedings of the third Eurographics symposium on Geometry processing, July 04-06, 2005, Vienna, Austria