Algorithms for detecting dependencies and rigid subsystems for CAD

DOI10.1016/J.CAGD.2016.06.001MaRDI QIDQ1634821zbMATH OpenOpenAlexFDO

Authors James Farre, Helena Kleinschmidt, Jessica Sidman, Audrey St. John, Stephanie Stark, Louis Theran, Xilin Yu

Publication date 18 December 2018

Published in Computer Aided Geometric Design (Search for Journal in Brave)

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

zbMATH Keywords

pebble game algorithmCAD constraintssparsity matroid

Mathematics Subject Classification ID

Computer science aspects of computer-aided design (68U07) Combinatorial aspects of matroids and geometric lattices (05B35) Computer-aided design (modeling of curves and surfaces) (65D17)

Abstract: Geometric constraint systems underly popular Computer Aided Design soft- ware. Automated approaches for detecting dependencies in a design are critical for developing robust solvers and providing informative user feedback, and we provide algorithms for two types of dependencies. First, we give a pebble game algorithm for detecting generic dependencies. Then, we focus on identifying the "special positions" of a design in which generically independent constraints become dependent. We present combinatorial algorithms for identifying subgraphs associated to factors of a particular polynomial, whose vanishing indicates a special position and resulting dependency. Further factoring in the Grassmann- Cayley algebra may allow a geometric interpretation giving conditions (e.g., "these two lines being parallel cause a dependency") determining the special position.

Recommendations

• Detecting All Dependences in Systems of Geometric Constraints Using the Witness Method
• Geometric constraint solving: the witness configuration method
• scientific article; zbMATH DE number 1163555
• Interrogating witnesses for geometric constraint solving
• Body-and-cad geometric constraint systems

Cites work

• scientific article; zbMATH DE number 3959442 (Why is no real title available?)
• scientific article; zbMATH DE number 41286 (Why is no real title available?)
• scientific article; zbMATH DE number 952952 (Why is no real title available?)
• A family of exceptional Stewart-Gough mechanisms of genus 7
• Algorithms in invariant theory
• Body-and-cad geometric constraint systems
• Characterizing generic global rigidity
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Detecting All Dependences in Systems of Geometric Constraints Using the Witness Method
• Edge-Disjoint Spanning Trees of Finite Graphs
• Multilinear Cayley factorization
• On graphs and rigidity of plane skeletal structures
• On the Problem of Decomposing a Graph into n Connected Factors
• Pebble game algorithms and sparse graphs
• Rigidity of multi-graphs. I: Linking rigid bodies in n-space
• Sparsity-certifying graph decompositions
• The Algebraic Geometry of Motions of Bar-and-Body Frameworks
• The Union of Matroids and the Rigidity of Frameworks

Cited in

(2)

• Detecting All Dependences in Systems of Geometric Constraints Using the Witness Method
• Foreword to special issue

Describes a project that uses

Uses Software

• StewartGoughGenus7

This page was built for publication: Algorithms for detecting dependencies and rigid subsystems for CAD

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