Algorithms for Identifying Rigid Subsystems in Geometric Constraint Systems
Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 233-237.
Abstract
The structural rigidity property, a generalization of Laman 's theorem which characterizes rigid bar frameworks in 2D, is generally considered a good approximation of rigidity in geometric constraint satisfaction problems (GCSPs). However, it may fail even on simple GCSPs because it does not take geometric properties into account. In this paper, we question the flow-based algorithm used by Hoffmann et al. to identify rigid subGCSPs. We show that this algorithm may fail because of the structural rigidity, but also by design. We introduce a new flow-based algorithm which uses Jermann et a!. 's characterization of rigidity. We show that this algorithm is correct in 2D and 3D, and can be used to tackle the major issues related to rigidity: deciding whether a GCSP is rigid or not and identifying rigid (or over-rigid) subGCSPs.
@inproceedings{ijcai2003p34,
title = {Algorithms for Identifying Rigid Subsystems in Geometric Constraint Systems},
author = {Jermann, Christophe and Neveu, Bertrand and Trombettoni, Gilles},
booktitle = {Proceedings of the Eighteenth International Joint Conference on
Artificial Intelligence, {IJCAI-03}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Georg Gottlob},
pages = {233--237},
year = {2003},
url = {https://ijcai.org/proceedings/2003/34},
}
TY - CPAPER TI - Algorithms for Identifying Rigid Subsystems in Geometric Constraint Systems AU - Jermann, Christophe AU - Neveu, Bertrand AU - Trombettoni, Gilles T2 - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03 PB - International Joint Conferences on Artificial Intelligence PY - 2003 SP - 233 EP - 237 UR - https://ijcai.org/proceedings/2003/34 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
