Enumerating constrained non-crossing minimally rigid frameworks

DOI10.1007/s00454-007-9026-xzbMath1147.52007arXivmath/0608102OpenAlexW1995366441MaRDI QIDQ946684

David Avis, Makoto Ohsaki, Naoki Katoh, Ileana Streinu, Shin-ichi Tanigawa

Publication date: 24 September 2008

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

rigidityconstrained Delaunay triangulationconstrained non-crossing minimally rigid frameworksgeometric enumeration

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Related Items

Improving upper and lower bounds for the total number of edge crossings of Euclidean minimum weight Laman graphs, Fast enumeration algorithms for non-crossing geometric graphs, Enumerating edge-constrained triangulations and edge-constrained non-crossing geometric spanning trees

Cites Work

• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra
• The complexity of detecting crossingfree configurations in the plane
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Enumerating pseudo-triangulations in the plane
• Reverse search for enumeration
• Enumerating non-crossing minimally rigid frameworks
• Gray code enumeration of plane straight-line graphs
• On graphs and rigidity of plane skeletal structures
• Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time
• Acute triangulations of polygons
• Algorithms - ESA 2003
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item