Aichholzer, Oswin; Hackl, Thomas; Orden, David; Pilz, Alexander; Saumell, Maria; Vogtenhuber, Birgit Flips in combinatorial pointed pseudo-triangulations with face degree at most four. (English) Zbl 1327.68307 Int. J. Comput. Geom. Appl. 24, No. 3, 197-224 (2014). 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. Cited in 1 ReviewCited in 2 Documents MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) Keywords:pointed pseudo-triangulation; combinatorial pseudo-triangulation; flip graph; graph diameter; bounded face degree PDFBibTeX XMLCite \textit{O. Aichholzer} et al., Int. J. Comput. Geom. Appl. 24, No. 3, 197--224 (2014; Zbl 1327.68307) 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.