Enumerating pseudo-triangulations in the plane

DOI10.1016/J.COMGEO.2004.09.002MaRDI QIDQ1776895zbMATH OpenOpenAlexFDO

Authors 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

flipsgraphpseudo-triangulationsreverse searchspanning tree

Mathematics Subject Classification ID

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

Review text

An algorithm for enumerating all pointed pseudo-triangulations of a set of \(n\) points in the plane is presented. It uses flips to generate pseudo-triangulations, it is based on a reverse search technique, and its running time is O\((\log n)\) per pseudo-triangulation. It can be used also to list the vertices of the polytope of pointed pseudo-triangulations. Moreover, it generates a spanning tree of the graph of pseudo-triangulations.

Recommendations

• On numbers of pseudo-triangulations
• On the number of pseudo-triangulations of certain point sets
• Counting triangulations of planar point sets
• Parallel enumeration of triangulations
• scientific article; zbMATH DE number 1741017
• ENUMERATING TRIANGULATIONS IN GENERAL DIMENSIONS
• Combinatorial pseudo-triangulations
• Enumeration of unicursal planar near-triangulation.
• Enumerating triangulations by parallel diagonals
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm

Cites work

• Algorithms and Data Structures
• An efficient algorithm for enumeration of triangulations
• Convexity minimizes pseudo-triangulations
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• Flipping edges in triangulations
• scientific article; zbMATH DE number 501471 (Why is no real title available?)
• scientific article; zbMATH DE number 2009873 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• scientific article; zbMATH DE number 2209740 (Why is no real title available?)
• Introduction to algorithms
• Kinetic collision detection for simple polygons
• Maintenance of configurations in the plane
• Reverse search for enumeration
• Straightening polygonal arcs and convexifying polygonal cycles
• THE VISIBILITY COMPLEX
• Topologically sweeping visibility complexes via pseudotriangulations

Cited in

(36)

• The enumeration of akempic triangulations
• On the number of triangles in simple arrangements of pseudolines in the real projective plane
• The polytope of non-crossing graphs on a planar point set
• Planar minimally rigid graphs and pseudo-triangulations
• An efficient algorithm for enumeration of triangulations
• On numbers of pseudo-triangulations
• Algorithmic enumeration of surrounding polygons
• Enumeration of planar constellations with an alternating boundary
• Convex dominating sets in maximal outerplanar graphs
• Enumerating non-crossing minimally rigid frameworks
• Transforming pseudo-triangulations
• Gray code enumeration of plane straight-line graphs
• On the number of pseudo-triangulations of certain point sets
• Why do simple algorithms for triangle enumeration work in the real world?
• Counting and Enumerating Pointed Pseudotriangulations with the Greedy Flip Algorithm
• Pseudo-triangulations -- a survey
• scientific article; zbMATH DE number 2009873 (Why is no real title available?)
• Multitriangulations, pseudotriangulations and primitive sorting networks
• Enumeration of Inner Leafless Planar Near-quadrangulations
• The polytope of non-crossing graphs on a planar point set
• The diameter of type \(D\) associahedra and the non-leaving-face property
• scientific article; zbMATH DE number 6415711 (Why is no real title available?)
• Flips in combinatorial pointed pseudo-triangulations with face degree at most four
• Planar minimally rigid graphs and pseudo-triangulations
• scientific article; zbMATH DE number 2209740 (Why is no real title available?)
• Fast enumeration algorithms for non-crossing geometric graphs
• Enumerating triangulation paths
• The stochastic walk algorithms for point location in pseudo-triangulations
• Amortized efficiency of generating planar paths in convex position
• Flips in edge-labelled pseudo-triangulations
• Computing pseudotriangulations via branched coverings
• Empty pseudo-triangles in point sets
• Combinatorial pseudo-triangulations
• 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

This page was built for publication: Enumerating pseudo-triangulations in the plane

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