×

Flips in combinatorial pointed pseudo-triangulations with face degree at most four. (English) Zbl 1327.68307

Summary: In this paper we consider the flip 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 flip graph of combinatorial 4-PPTs is connected and has diameter \(O(n^2)\), even in the case of labeled vertices with fixed outer face. For this case we provide an \(\Omega(n \log n)\) lower bound.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aichholzer O., EuroCG 2010 pp 21– (2010)
[2] DOI: 10.1137/S0097539702411368 · Zbl 1041.68105 · doi:10.1137/S0097539702411368
[3] DOI: 10.1016/j.ipl.2004.01.021 · Zbl 1177.68236 · doi:10.1016/j.ipl.2004.01.021
[4] DOI: 10.1016/j.comgeo.2008.04.001 · Zbl 1146.05016 · doi:10.1016/j.comgeo.2008.04.001
[5] DOI: 10.1137/050631008 · Zbl 1120.68104 · doi:10.1137/050631008
[6] DOI: 10.1007/PL00009464 · Zbl 0939.68135 · doi:10.1007/PL00009464
[7] DOI: 10.1016/S0925-7721(02)00126-8 · Zbl 1023.65013 · doi:10.1016/S0925-7721(02)00126-8
[8] Komuro H., Yokohama Math. J. 44 (2) pp 115–
[9] DOI: 10.1016/j.disc.2005.09.045 · Zbl 1109.05037 · doi:10.1016/j.disc.2005.09.045
[10] DOI: 10.1090/S0894-0347-1988-0928904-4 · doi:10.1090/S0894-0347-1988-0928904-4
[11] Streinu I., IEEE Computer Society 200 pp 443–
[12] Wagner K., Deutschen Mathematiker-Vereinigung 46 pp 26– (1936)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.