Flips in combinatorial pointed pseudo-triangulations with face degree at most four

Oswin Aichholzer, Thomas Hackl, David Orden, Alexander Pilz, Maria Saumell, Birgit Vogtenhuber

Publikation: Beitrag in einer FachzeitschriftArtikelBegutachtung

Abstract

In this paper we consider the ip operation for combinatorial pointed pseudotriangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs.We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the ip graph of combinatorial 4-PPTs is connected and has diameter O(n2), even in the case of labeled vertices with fixed outer face. For this case we provide an Ω(n log n) lower bound.
Originalspracheenglisch
Seiten (von - bis)197-224
FachzeitschriftInternational Journal of Computational Geometry and Applications
Jahrgang24
Ausgabenummer3
DOIs
PublikationsstatusVeröffentlicht - 2014

Fields of Expertise

  • Information, Communication & Computing

Treatment code (Nähere Zuordnung)

  • Theoretical

Fingerprint

Untersuchen Sie die Forschungsthemen von „Flips in combinatorial pointed pseudo-triangulations with face degree at most four“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren