Flips in edge-labelled pseudo-triangulations

DOI10.1016/J.COMGEO.2016.08.001MaRDI QIDQ680154zbMATH OpenOpenAlexFDO

Authors Prosenjit Bose, Sander Verdonschot

Publication date 22 January 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.01485

zbMATH Keywords

diagonal flipedge flippseudo-triangulationedge-label

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Abstract: We show that $O(n^2)$ exchanging flips suffice to transform any edge-labelled pointed pseudo-triangulation into any other with the same set of labels. By using insertion, deletion and exchanging flips, we can transform any edge-labelled pseudo-triangulation into any other with $O(nlogc+hlogh)$ flips, where $c$ is the number of convex layers and $h$ is the number of points on the convex hull.

Recommendations

• scientific article; zbMATH DE number 2009873
• Transforming pseudo-triangulations
• Flipping edges in triangulations
• Enumerating pseudo-triangulations in the plane
• scientific article; zbMATH DE number 2187697

Cites work

• Acute triangulations of polygons
• Colorful associahedra and cyclohedra
• Flipping edge-labelled triangulations
• Flipping edges in triangulations
• KINETIC COLLISION DETECTION FOR SIMPLE POLYGONS
• Pseudo-triangulations -- a survey
• Pseudotriangulations from Surfaces and a Novel Type of Edge Flip
• Transforming pseudo-triangulations
• Transforming spanning trees and pseudo-triangulations
• Transforming triangulations

Cited in

(8)

• A proof of the orbit conjecture for flipping edge-labelled triangulations
• A proof of the orbit conjecture for flipping edge-labelled triangulations
• Pseudotriangulations from Surfaces and a Novel Type of Edge Flip
• scientific article; zbMATH DE number 2187697 (Why is no real title available?)
• Algorithms and Data Structures
• scientific article; zbMATH DE number 2009873 (Why is no real title available?)
• Flips in combinatorial pointed pseudo-triangulations with face degree at most four
• Transforming pseudo-triangulations

This page was built for publication: Flips in edge-labelled pseudo-triangulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q680154)