Algorithms for detecting dependencies and rigid subsystems for CAD

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

doi:10.1016/j.cagd.2016.06.001

Algorithms for detecting dependencies and rigid subsystems for CAD

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

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	130-149
Number of pages	20
Journal	Computer Aided Geometric Design
Volume	47
Early online date	28 Jun 2016
DOIs	https://doi.org/10.1016/j.cagd.2016.06.001
Publication status	Published - 1 Oct 2016

Keywords

Sparsity matroid
Pebble game algorithm
Cad constraints

Access to Document

10.1016/j.cagd.2016.06.001

Theran_2016_CAGD_CAD_AM
© 2016, Elsevier. This work is made available online in accordance with the publisher’s policies. This is the author created, accepted version manuscript following peer review and may differ slightly from the final published version. The final published version of this work is available at www.sciencedirect.com / https://dx.doi.org/10.1016/j.cagd.2016.06.001
Accepted author manuscript, 1.13 MB

Cite this

@article{27d1fc6526424eaeb4752f0a3adf8261,

title = "Algorithms for detecting dependencies and rigid subsystems for CAD",

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.",

keywords = "Sparsity matroid, Pebble game algorithm, Cad constraints",

author = "James Farre and Helena Kleinschmidt and Jessica Sidman and John, {Audrey St.} and Stephanie Stark and Louis Theran and Xilin Yu",

note = "Louis Theran is partially supported by the European Research Council under the European Union{\textquoteright}s Seventh Framework Programme (FP7/2007–2013)/ERC grant agreement No. 247029-SDModels, Academy of Finland (AKA) project COALESCE, and the Hutchcroft fund.",

year = "2016",

month = oct,

day = "1",

doi = "10.1016/j.cagd.2016.06.001",

language = "English",

volume = "47",

pages = "130--149",

journal = "Computer Aided Geometric Design",

issn = "0167-8396",

publisher = "Elsevier",

}

TY - JOUR

T1 - Algorithms for detecting dependencies and rigid subsystems for CAD

AU - Farre, James

AU - Kleinschmidt, Helena

AU - Sidman, Jessica

AU - John, Audrey St.

AU - Stark, Stephanie

AU - Theran, Louis

AU - Yu, Xilin

N1 - Louis Theran is partially supported by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007–2013)/ERC grant agreement No. 247029-SDModels, Academy of Finland (AKA) project COALESCE, and the Hutchcroft fund.

PY - 2016/10/1

Y1 - 2016/10/1

N2 - 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.

AB - 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.

KW - Sparsity matroid

KW - Pebble game algorithm

KW - Cad constraints

U2 - 10.1016/j.cagd.2016.06.001

DO - 10.1016/j.cagd.2016.06.001

M3 - Article

SN - 0167-8396

VL - 47

SP - 130

EP - 149

JO - Computer Aided Geometric Design

JF - Computer Aided Geometric Design

ER -

Algorithms for detecting dependencies and rigid subsystems for CAD

Abstract

Keywords

Access to Document

Fingerprint

Cite this