A characterisation of the generic rigidity of 2-dimensional point-line frameworks

DOI10.1016/J.JCTB.2015.12.007MaRDI QIDQ273172zbMATH OpenOpenAlexFDO

Authors Bill Jackson, J. C. Owen

Publication date 21 April 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

submodular functioncombinatorial rigiditycount matroidDilworth truncationmatroid unionpoint-line frameworkpolynomial algorithm

Mathematics Subject Classification ID

Rigidity and flexibility of structures (aspects of discrete geometry) (52C25)

Abstract: A 2-dimensional point-line framework is a collection of points and lines in the plane which are linked by pairwise constraints that fix some angles between pairs of lines and also some point-line and point-point distances. It is rigid if every continuous motion of the points and lines which preserves the constraints results in a point-line framework which can be obtained from the initial framework by a translation or a rotation. We characterise when a generic point-line framework is rigid. Our characterisation gives rise to a polynomial algorithm for solving this decision problem.

Recommendations

• Global rigidity of 2D linearly constrained frameworks
• Coincident rigidity of 2-dimensional frameworks
• scientific article; zbMATH DE number 6606168
• The rigidity of generalized rectangular frameworks
• Rigid two-dimensional frameworks with two coincident points
• Rigidity of linearly constrained frameworks
• An improved bound for the rigidity of linearly constrained frameworks
• Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids
• A characterization of generically rigid frameworks on surfaces of revolution
• A sufficient connectivity condition for rigidity and global rigidity of linearly constrained frameworks in \(\mathbb{R}^2\)

Cites work

• scientific article; zbMATH DE number 3959442 (Why is no real title available?)
• scientific article; zbMATH DE number 67319 (Why is no real title available?)
• scientific article; zbMATH DE number 3604926 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A characterisation of the generic rigidity of 2-dimensional point-line frameworks
• A matroid on hypergraphs, with applications in scene analysis and geometry
• A rooted-forest partition with uniform vertex demand
• Algorithms for graph rigidity and scene analysis
• An algorithm for two-dimensional rigidity percolation: The pebble game
• Automated Deduction in Geometry
• CONSTRAINTS ON SIMPLE GEOMETRY IN TWO AND THREE DIMENSIONS
• Connected rigidity matroids and unique realizations of graphs
• Connections in combinatorial optimization
• Detection of structural inconsistency in systems of equations with degrees of freedom and its applications
• Forests, frames, and games: Algorithms for matroid sums and applications
• Generic global rigidity
• Geometric constraint solver
• MATROIDS AND SUBMODULAR FUNCTIONS
• Minimum partition of a matroid into independent subsets
• On Generic Rigidity in the Plane
• On combinatorial structures of line drawings of polyhedra
• On graphs and rigidity of plane skeletal structures
• On the determinacy of repetitive structures.
• Pebble game algorithms and sparse graphs
• Submodular functions and independence structures
• The Rigidity of Graphs
• The Union of Matroids and the Rigidity of Frameworks
• Transversals and matroid partition

Cited in

(14)

• A characterisation of the generic rigidity of 2-dimensional point-line frameworks
• scientific article; zbMATH DE number 1556960 (Why is no real title available?)
• Configurations of lines in space and combinatorial rigidity
• Pairing symmetries for Euclidean and spherical frameworks
• Rigidity of linearly constrained frameworks
• Analyzing rigidity with pebble games
• Radically solvable graphs
• An improved bound for the rigidity of linearly constrained frameworks
• When is a planar rod configuration infinitesimally rigid?
• Point-hyperplane frameworks, slider joints, and rigidity preserving transformations
• Epsilon local rigidity and numerical algebraic geometry
• scientific article; zbMATH DE number 6606168 (Why is no real title available?)
• Stability of \(\mathbb{Z}^2\) configurations in 3D
• Rigid two-dimensional frameworks with three collinear points

This page was built for publication: A characterisation of the generic rigidity of 2-dimensional point-line frameworks

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