Computational complexity of combinatorial surfaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computational complexity of combinatorial surfaces

Full text

Pdf (867 KB)

Source

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

Berkley, California, United States

Pages: 102 - 111

Year of Publication: 1990

ISBN:0-89791-362-0

Authors

Gert Vegter	Department of Computing Science, University of Groningen, P.O.Box 800, 9700 AV Groningen, The Netherlands
Chee K. Yap	Fachbereich Mathematik, Freie Universitaet Berlin, Arnimallee 2-6, 1000 Berlin 33 West Germany

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): 7, Downloads (12 Months): 36, Citation Count: 23

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/98524.98546 What is a DOI?

ABSTRACT

We investigate the computational problems associated with combinatorial surfaces. Specifically, we present an algorithm (based on the Brahana-Dehn-Heegaard approach) for transforming the polygonal schema of a closed triangulated surface into its canonical form in &Ogr;(n log n) time, where n is the total number of vertices, edges and faces. We also give an &Ogr;(n log n + gn) algorithm for constructing canonical generators of the fundamental group of a surface of genus g. This is useful in constructing homeomorphisms between combinatorial surfaces.

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.

	1	H.R. Brahana. Systems of circuits on two-dlmensional manifolds. Ann. Math., 23:144-68, 1922.
	2	Maurice Fr~chet and Ky Fan. Initiation to Combinatorial Topology. Prindle, Weber and Schmidt, Inc., Boston, Massachusetts, 1934. Translated from French, with notes by Howard E. Eves.
	3	F. Harary. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
	4	Wi}Ham S. Massey. Algebraic Topology: An Introduction. Graduate Texts in Mathematics, Vol. 56. Springer-Verlag, 1977.
	5	Kurt Mehlhorn , Chee-Keng Yap, Constructive Hopf's Theorem: Or How to Untangle Closed Planar Curves, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.410-423, July 11-15, 1988
	6	3. R. Munkres. Element8 of Algebraic Topology. Addison-Wesley, Menlo-Park, California, 1984.
	7	3. StillweH. Classical Topology and Combinatorial Group Theory. Springer-Verlag, New York, 1980.
	8	G. Vegter, Kink-free deformations of polygons, Proceedings of the fifth annual symposium on Computational geometry, p.61-68, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73840]

CITED BY 23

	Jeff Erickson , Sariel Har-Peled, Optimally cutting a surface into a disk, Proceedings of the eighteenth annual symposium on Computational geometry, p.244-253, June 05-07, 2002, Barcelona, Spain
	Tamal K. Dey , Sumanta Guha, Computing homology groups of simplicial complexes in R3, Journal of the ACM (JACM), v.45 n.2, p.266-287, March 1998
	Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	Tamal K. Dey , Sumanta Guha, Algorithms for manifolds and simplicial complexes in Euclidean 3-space (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.398-407, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Xianfeng Gu , Shing-Tung Yau, Global conformal surface parameterization, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	David Eppstein, Dynamic generators of topologically embedded graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Tula Ram Ban , Dibakar Sen, Graph based topological analysis of tessellated surfaces, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	Franck Hétroy , Dominique Attali, Topological quadrangulations of closed triangulated surfaces using the Reeb graph, Graphical Models, v.65 n.1-3, p.131-148, January 2003
	Zoë Wood , Hugues Hoppe , Mathieu Desbrun , Peter Schröder, Removing excess topology from isosurfaces, ACM Transactions on Graphics (TOG), v.23 n.2, p.190-208, April 2004
	Haijo Schipper, Determining contractibility of curves, Proceedings of the eighth annual symposium on Computational geometry, p.358-367, June 10-12, 1992, Berlin, Germany
	Tamal K. Dey, A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection, Proceedings of the tenth annual symposium on Computational geometry, p.277-284, June 06-08, 1994, Stony Brook, New York, United States
	Éric Colin de Verdière , Jeff Erickson, Tightening non-simple paths and cycles on surfaces, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.192-201, January 22-26, 2006, Miami, Florida
	Craig Gotsman , Kanela Kaligosi , Kurt Mehlhorn , Dimitrios Michail , Evangelia Pyrga, Cycle bases of graphs and sampled manifolds, Computer Aided Geometric Design, v.24 n.8-9, p.464-480, November, 2007
	S. Biasotti , D. Giorgi , M. Spagnuolo , B. Falcidieno, Reeb graphs for shape analysis and applications, Theoretical Computer Science, v.392 n.1-3, p.5-22, February, 2008
	Francis Lazarus , Michel Pocchiola , Gert Vegter , Anne Verroust, Computing a canonical polygonal schema of an orientable triangulated surface, Proceedings of the seventeenth annual symposium on Computational geometry, p.80-89, June 2001, Medford, Massachusetts, United States
	G. Patanè , M. Spagnuolo , B. Falcidieno, Families of cut-graphs for bordered meshes with arbitrary genus, Graphical Models, v.69 n.2, p.119-138, March, 2007
	Ken-ichi Kawarabayashi , Bojan Mohar, Graph and map isomorphism and all polyhedral embeddings in linear time, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Ken-ichi Kawarabayashi , Buce Reed, Computing crossing number in linear time, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Éric Colin De Verdière , Francis Lazarus, Optimal pants decompositions and shortest homotopic cycles on an orientable surface, Journal of the ACM (JACM), v.54 n.4, p.18-es, July 2007
	Luca Castelli Aleardi , Eric Fusy , Thomas Lewiner, Schnyder woods for higher genus triangulated surfaces, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Afra Zomorodian , Gunnar Carlsson, Localized homology, Computational Geometry: Theory and Applications, v.41 n.3, p.126-148, November, 2008
	S. Biasotti , L. De Floriani , B. Falcidieno , P. Frosini , D. Giorgi , C. Landi , L. Papaleo , M. Spagnuolo, Describing shapes by geometrical-topological properties of real functions, ACM Computing Surveys (CSUR), v.40 n.4, p.1-87, October 2008