Computational complexity of combinatorial surfaces

Gert Vegter, Chee K. Yap

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 O(n log n) time, where n is the total number of vertices, edges and faces. We also give an O(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.

Original languageEnglish (US)
Title of host publicationProc Sixth Annu Symp Comput Geom
PublisherPubl by ACM
Pages102-111
Number of pages10
ISBN (Print)0897913620, 9780897913621
DOIs
StatePublished - 1990
EventProceedings of the Sixth Annual Symposium on Computational Geometry - Berkeley, CA, USA
Duration: Jun 6 1990Jun 8 1990

Publication series

NameProc Sixth Annu Symp Comput Geom

Conference

ConferenceProceedings of the Sixth Annual Symposium on Computational Geometry
CityBerkeley, CA, USA
Period6/6/906/8/90

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Computational complexity of combinatorial surfaces'. Together they form a unique fingerprint.

  • Cite this

    Vegter, G., & Yap, C. K. (1990). Computational complexity of combinatorial surfaces. In Proc Sixth Annu Symp Comput Geom (pp. 102-111). (Proc Sixth Annu Symp Comput Geom). Publ by ACM. https://doi.org/10.1145/98524.98546