2021/06/28 by Thomas Dagès, Alfred M. Bruckstein⋆, Dagès, Thomas +1
Computer Science · Mathematics · #05C10 #68R10 #68U05 #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Mathematics and Applications
paper · pdf · doi:10.48550/arxiv.2106.14408
openalex publication_date 2021/06/28 · openalex created_date 2021/07/05 · openalex updated_date 2026/07/28
We revisit here a fundamental result on planar triangulations, namely that the flip distance between two triangulations is upper-bounded by the number of proper intersections between their straight-segment edges. We provide a complete and detailed proof of this result in a slightly generalised setting using a case-based analysis that fills several gaps left by previous proofs of the result.