Enumerating pseudo-triangulations in the plane

DOI10.1016/j.comgeo.2004.09.002zbMath1071.65017OpenAlexW2005421767MaRDI QIDQ1776895

Sergey Bereg

Publication date: 12 May 2005

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2004.09.002

zbMATH Keywords

graphspanning treeflipspseudo-triangulationsreverse search

Mathematics Subject Classification ID

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

Related Items

Enumerating non-crossing minimally rigid frameworks, Multitriangulations, pseudotriangulations and primitive sorting networks, Decomposing a simple polygon into pseudo-triangles and convex polygons, Fast enumeration algorithms for non-crossing geometric graphs, Gray code enumeration of plane straight-line graphs, The diameter of type \(D\) associahedra and the non-leaving-face property, Enumerating constrained non-crossing minimally rigid frameworks, Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees, Convex dominating sets in maximal outerplanar graphs

Cites Work

• Convexity minimizes pseudo-triangulations
• Maintenance of configurations in the plane
• Straightening polygonal arcs and convexifying polygonal cycles
• Flipping edges in triangulations
• Topologically sweeping visibility complexes via pseudotriangulations
• An efficient algorithm for enumeration of triangulations
• Reverse search for enumeration
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• Kinetic collision detection for simple polygons
• THE VISIBILITY COMPLEX
• Algorithms and Data Structures
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item