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

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

doi:10.1142/S0218195914600036

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

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

Institute of Software Technology (7160)

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	197-224
Journal	International Journal of Computational Geometry and Applications
Volume	24
Issue number	3
DOIs	https://doi.org/10.1142/S0218195914600036
Publication status	Published - 2014

Fields of Expertise

Information, Communication & Computing

Treatment code (Nähere Zuordnung)

Theoretical

Access to Document

10.1142/S0218195914600036

1 Active
2 Finished

Discrete and Computational Geometry
Hackl, T., Aigner, W., Pilz, A., Vogtenhuber, B., Kornberger, B. & Aichholzer, O.
1/01/05 → 31/12/24
Project: Research area
FWF - ComPoSe - EuroGIAG_Erdös-Szekeres type problems for colored point sets and compatible graphs
Aichholzer, O.
1/10/11 → 31/12/15
Project: Research project
FWF - CPGG - Combinatorial Problems on Geometric Graphs
Hackl, T.
1/09/11 → 31/12/15
Project: Research project

Cite this

@article{7e15b15c65bc4557b033e0eaa73ad368,

title = "Flips in combinatorial pointed pseudo-triangulations with face degree at most four",

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.",

author = "Oswin Aichholzer and Thomas Hackl and David Orden and Alexander Pilz and Maria Saumell and Birgit Vogtenhuber",

year = "2014",

doi = "10.1142/S0218195914600036",

language = "English",

volume = "24",

pages = "197--224",

journal = "International Journal of Computational Geometry and Applications",

publisher = "World Scientific ",

number = "3",

}

TY - JOUR

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

AU - Aichholzer, Oswin

AU - Hackl, Thomas

AU - Orden, David

AU - Pilz, Alexander

AU - Saumell, Maria

AU - Vogtenhuber, Birgit

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.1142/S0218195914600036

DO - 10.1142/S0218195914600036

M3 - Article

VL - 24

SP - 197

EP - 224

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 3

ER -

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

Abstract

Fields of Expertise

Treatment code (Nähere Zuordnung)

Access to Document

Fingerprint

Projects

Discrete and Computational Geometry

FWF - ComPoSe - EuroGIAG_Erdös-Szekeres type problems for colored point sets and compatible graphs

FWF - CPGG - Combinatorial Problems on Geometric Graphs

Cite this