Publication

Computational Complexity of Combinatorial Surfaces

Vegter, G. & Yap, C. K., 1990, EPRINTS-BOOK-TITLE. University of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science, 10 p.

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

Copy link to clipboard

Documents

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
Title of host publicationEPRINTS-BOOK-TITLE
PublisherUniversity of Groningen, Johann Bernoulli Institute for Mathematics and Computer Science
Number of pages10
Publication statusPublished - 1990

Download statistics

No data available

ID: 3354077