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

DOI10.1016/J.JCTB.2015.12.007zbMATH Open1338.52021arXiv1407.4675OpenAlexW286270710MaRDI QIDQ273172FDOQ273172

Authors: Bill Jackson, J. C. Owen 

Publication date: 21 April 2016

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

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.

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

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\)

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)

Cites Work

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

Cited In (14)

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

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)