Enumerating pseudo-triangulations in the plane

DOI10.1016/j.comgeo.2004.09.002zbMath1071.65017MaRDI 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

graph; spanning tree; flips; pseudo-triangulations; reverse search

Mathematics Subject Classification ID

05C05: Trees

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

Related Items

Fast enumeration algorithms for non-crossing geometric graphs, Decomposing a simple polygon into pseudo-triangles and convex polygons, Enumerating constrained non-crossing minimally rigid frameworks, Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees, Enumerating non-crossing minimally rigid frameworks, Gray code enumeration of plane straight-line graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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