Skip to content

Research at St Andrews

Algorithms for detecting dependencies and rigid subsystems for CAD

Research output: Contribution to journalArticle

Author(s)

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

School/Research organisations

Abstract

Automated approaches for detecting dependencies in structures created with Computer Aided Design software are critical for developing robust solvers and providing informative user feedback. We model a set of geometric constraints with a bi-colored multigraph and give a graph-based pebble game algorithm that allows us to determine combinatorially if there are generic dependencies. We further use the pebble game to yield a decomposition of the graph into factor graphs which may be used to give a user detailed feedback about dependent substructures in a specific realization of a system of CAD constraints with non-generic properties.
Close

Details

Original languageEnglish
Pages (from-to)130-149
Number of pages20
JournalComputer Aided Geometric Design
Volume47
Early online date28 Jun 2016
DOIs
Publication statusPublished - 1 Oct 2016

    Research areas

  • Sparsity matroid, Pebble game algorithm, Cad constraints

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Generic unlabeled global rigidity

    Gortler, S., Theran, L. & Thurston, D., 30 Jul 2019, In : Forum of Mathematics, Sigma. 7, 34 p., e21.

    Research output: Contribution to journalArticle

  2. Rigidity for sticky disks

    Connelly, R., Gortler, S. J. & Theran, L. S., 27 Feb 2019, In : Proceedings of the Royal Society A - Mathematical, Physical & Engineering Sciences. 475, 2222, 16 p., 20180773.

    Research output: Contribution to journalArticle

  3. Generically globally rigid graphs have generic universally rigid frameworks

    Connelly, R., Gortler, S. & Theran, L. S., 14 Aug 2018, (Accepted/In press) In : Combinatorica.

    Research output: Contribution to journalArticle

  4. Affine rigidity and conics at infinity

    Connelly, R., Gortler, S. J. & Theran, L., Jul 2018, In : International Mathematics Research Notices. 2018, 13, p. 4084-4102 19 p.

    Research output: Contribution to journalArticle

  5. Analytic analysis of auxetic metamaterials through analogy with rigid link systems

    Rayneau-Kirkhope, D., Zhang, C., Theran, L. S. & Dias, M., 21 Feb 2018, In : Proceedings of the Royal Society A - Mathematical, Physical & Engineering Sciences. 474, 2210, 12 p., 20170753.

    Research output: Contribution to journalArticle

ID: 243729739

Top