Computing a canonical polygonal schema of an orientable triangulated surface

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computing a canonical polygonal schema of an orientable triangulated surface

Full text

Pdf (503 KB)

Source

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

Medford, Massachusetts, United States

Pages: 80 - 89

Year of Publication: 2001

ISBN:1-58113-357-X

Authors

Francis Lazarus	CNRS and University of Poitiers, France
Michel Pocchiola	Dépt d'Informatique, Ecole Normale Supérieure, Paris, France
Gert Vegter	Dept. of Math. and CS, University of Groningen, The Netherlands
Anne Verroust	INRIA Rocquencourt, France

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): 8, Downloads (12 Months): 30, Citation Count: 31

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

ABSTRACT

A closed orientable surface of genus $g$ can be obtained by appropriat e identification of pairs of edges of a $4g$-gon (the polygonal schema). The identified edges form $2g$ loops on the surface, that are disjoint except for their common end-point. These loops are generators of both the fundamental group and the homology group of the surface. The inverse problem is concerned with finding a set of $2g$ loops on a triangulated surface, such that cutting the surface along these loops yields a (canonical) polygonal schema. We present two optimal algorithms for this inverse problem. Both algorithms have been implemented using the CGAL polyhedron data structure.

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	M. Armstrong. Basic Topology. Undergraduate Texts in Mathematics. Springer Verlag, Berlin, 1983.
	2	T. Brahana. Systems of circuits on 2-dimensional manifolds. Ann. Math., 23:144-168, 1921.
	3	Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
	4	Tamal K. Dey , Sumanta Guha, Transforming curves on surfaces, Journal of Computer and System Sciences, v.58 n.2, p.297-325, April 1999 [doi>10.1006/jcss.1998.1619]
	5	T. Dey, H. Edelsbrunner, and S. Guha. Computational topology. InAdvances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pages 109-143, 1999.
	6	T. Dey and H. Schipper. A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection. Discrete and Computational Geometry, 14:93-110, 1995.
	7	Lutz Kettner, Using generic programming for designing a data structure for polyhedral surfaces, Computational Geometry: Theory and Applications, v.13 n.1, p.65-90, May 1999 [doi>10.1016/S0925-7721(99)00007-3]
	8	J. Stillwell. Classical Topology and Combinatorial Group Theory. Springer-Verlag, New York, 1993.
	9	Gert Vegter, Computational topology, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	10	Gert Vegter , Chee K. Yap, Computational complexity of combinatorial surfaces, Proceedings of the sixth annual symposium on Computational geometry, p.102-111, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98546]

CITED BY 31

	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
	Pierre Alliez , Mark Meyer , Mathieu Desbrun, Interactive geometry remeshing, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
	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
	Jingqi Yan , Pengfei Shi , David Zhang, Transforming 3D mesh surfaces into images by parameterization, Integrated image and graphics technologies, Kluwer Academic Publishers, Norwell, MA, 2004
	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
	John Schreiner , Arul Asirvatham , Emil Praun , Hugues Hoppe, Inter-surface mapping, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
	Sunghee Choi, The Delaunay tetrahedralization from Delaunay triangulated surfaces, Proceedings of the eighteenth annual symposium on Computational geometry, p.145-150, June 05-07, 2002, Barcelona, Spain
	Eugene Zhang , Konstantin Mischaikow , Greg Turk, Feature-based surface parameterization and texture mapping, ACM Transactions on Graphics (TOG), v.24 n.1, p.1-27, January 2005
	Pierre Alliez , Éric Colin de Verdière , Olivier Devillers , Martin Isenburg, Centroidal Voronoi diagrams for isotropic surface remeshing, Graphical Models, v.67 n.3, p.204-231, May 2005
	É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
	Jeff Erickson , Kim Whittlesey, Greedy optimal homotopy and homology generators, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Xinlai Ni , Michael Garland , John C. Hart, Fair morse functions for extracting the topological structure of a surface mesh, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
	Wei Hong , Xianfeng Gu , Feng Qiu , Miao Jin , Arie Kaufman, Conformal virtual colon flattening, Proceedings of the 2006 ACM symposium on Solid and physical modeling, June 06-08, 2006, Cardiff, Wales, United Kingdom
	Erin W. Chambers , Éric Colin de Verdière , Jeff Erickson , Francis Lazarus , Kim Whittlesey, Splitting (complicated) surfaces is hard, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	M. Mortara , G. Patanè , M. Spagnuolo , B. Falcidieno , J. Rossignac, Plumber: a method for a multi-scale decomposition of 3D shapes into tubular primitives and bodies, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	D. Steiner , A. Fischer, Planar parameterization for closed 2-manifold genus-1 meshes, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Kai Hormann , Bruno Lévy , Alla Sheffer, Mesh parameterization: theory and practice Video files associated with this course are available from the citation page , ACM SIGGRAPH 2007 courses, August 05-09, 2007, San Diego, California
	Weishi Li , Ralph R. Martin , Frank C. Langbein, Generating smooth parting lines for mold design for meshes, Proceedings of the 2007 ACM symposium on Solid and physical modeling, June 04-06, 2007, Beijing, China
	Alla Sheffer , Emil Praun , Kenneth Rose, Mesh parameterization methods and their applications, Foundations and Trends® in Computer Graphics and Vision, v.2 n.2, p.105-171, January 2006
	Erin W. Chambers , Éric Colin de Verdière , Jeff Erickson , Francis Lazarus , Kim Whittlesey, Splitting (complicated) surfaces is hard, Computational Geometry: Theory and Applications, v.41 n.1-2, p.94-110, October, 2008
	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
	Miao Jin , Yalin Wang , Shing-Tung Yau , Xianfeng Gu, Optimal Global Conformal Surface Parameterization, Proceedings of the conference on Visualization '04, p.267-274, October 10-15, 2004
	É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
	Erin W. Chambers , Jeff Erickson , Pratik Worah, Testing contractibility in planar rips complexes, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	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
	Kai Hormann , Konrad Polthier , Alia Sheffer, Mesh parameterization: theory and practice, ACM SIGGRAPH ASIA 2008 courses, p.1-87, December 10-13, 2008, Singapore