Interrogating witnesses for geometric constraint solving

Dominique Michelucci; Sebti Foufou

doi:10.1145/1629255.1629301

Interrogating witnesses for geometric constraint solving

Dominique Michelucci, Sebti Foufou

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Classically, geometric constraint solvers use graph-based methods to analyze systems of geometric constraints. These methods have intrinsic limitations, which the witness method overcomes. This paper details the computation of a basis of the vector space of the free infinitesimal motions of a typical witness, and explains how to use this basis to interrogate the witness for detecting all dependencies between constraints: structural dependencies already detectable by graph-based methods, and also non-structural dependencies, due to known or unknown geometric theorems, which are undetectable with graph-based methods. The paper also discusses how to decide about the rigidity of a witness.

Original language	English (US)
Title of host publication	Proceedings - SPM 2009
Subtitle of host publication	SIAM/ACM Joint Conference on Geometric and Physical Modeling
Pages	343-348
Number of pages	6
DOIs	https://doi.org/10.1145/1629255.1629301
State	Published - 2009
Event	SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling - San Francisco, CA, United States Duration: Oct 5 2009 → Oct 8 2009

Publication series

Name	Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling

Other

Other	SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling
Country/Territory	United States
City	San Francisco, CA
Period	10/5/09 → 10/8/09

Keywords

Dependency detection
Geometric constraint solving

ASJC Scopus subject areas

Computational Theory and Mathematics
Computer Science Applications
Computer Vision and Pattern Recognition
General Mathematics

Access to Document

10.1145/1629255.1629301

Cite this

Interrogating witnesses for geometric constraint solving. / Michelucci, Dominique; Foufou, Sebti.
Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling. 2009. p. 343-348 1629301 (Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Michelucci, D & Foufou, S 2009, Interrogating witnesses for geometric constraint solving. in Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling., 1629301, Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling, pp. 343-348, SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling, San Francisco, CA, United States, 10/5/09. https://doi.org/10.1145/1629255.1629301

@inproceedings{2bcc627e7f864f49aec47e6e76c3f31c,

title = "Interrogating witnesses for geometric constraint solving",

abstract = "Classically, geometric constraint solvers use graph-based methods to analyze systems of geometric constraints. These methods have intrinsic limitations, which the witness method overcomes. This paper details the computation of a basis of the vector space of the free infinitesimal motions of a typical witness, and explains how to use this basis to interrogate the witness for detecting all dependencies between constraints: structural dependencies already detectable by graph-based methods, and also non-structural dependencies, due to known or unknown geometric theorems, which are undetectable with graph-based methods. The paper also discusses how to decide about the rigidity of a witness.",

keywords = "Dependency detection, Geometric constraint solving",

author = "Dominique Michelucci and Sebti Foufou",

note = "Funding Information: This research work has been funded by NPRP grant number NPRP-09-906-1-137 from the Qatar National Research Fund (a member of the Qatar Foundation).; SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling ; Conference date: 05-10-2009 Through 08-10-2009",

year = "2009",

doi = "10.1145/1629255.1629301",

language = "English (US)",

isbn = "9781605587110",

series = "Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling",

pages = "343--348",

booktitle = "Proceedings - SPM 2009",

}

TY - GEN

T1 - Interrogating witnesses for geometric constraint solving

AU - Michelucci, Dominique

AU - Foufou, Sebti

N1 - Funding Information: This research work has been funded by NPRP grant number NPRP-09-906-1-137 from the Qatar National Research Fund (a member of the Qatar Foundation).

PY - 2009

Y1 - 2009

N2 - Classically, geometric constraint solvers use graph-based methods to analyze systems of geometric constraints. These methods have intrinsic limitations, which the witness method overcomes. This paper details the computation of a basis of the vector space of the free infinitesimal motions of a typical witness, and explains how to use this basis to interrogate the witness for detecting all dependencies between constraints: structural dependencies already detectable by graph-based methods, and also non-structural dependencies, due to known or unknown geometric theorems, which are undetectable with graph-based methods. The paper also discusses how to decide about the rigidity of a witness.

AB - Classically, geometric constraint solvers use graph-based methods to analyze systems of geometric constraints. These methods have intrinsic limitations, which the witness method overcomes. This paper details the computation of a basis of the vector space of the free infinitesimal motions of a typical witness, and explains how to use this basis to interrogate the witness for detecting all dependencies between constraints: structural dependencies already detectable by graph-based methods, and also non-structural dependencies, due to known or unknown geometric theorems, which are undetectable with graph-based methods. The paper also discusses how to decide about the rigidity of a witness.

KW - Dependency detection

KW - Geometric constraint solving

UR - http://www.scopus.com/inward/record.url?scp=70350686583&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350686583&partnerID=8YFLogxK

U2 - 10.1145/1629255.1629301

DO - 10.1145/1629255.1629301

M3 - Conference contribution

AN - SCOPUS:70350686583

SN - 9781605587110

T3 - Proceedings - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling

SP - 343

EP - 348

BT - Proceedings - SPM 2009

T2 - SPM 2009: SIAM/ACM Joint Conference on Geometric and Physical Modeling

Y2 - 5 October 2009 through 8 October 2009

ER -

Interrogating witnesses for geometric constraint solving

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this