Characterizing 1-dof Henneberg-I graphs with efficient configuration spaces

ABSTRACT

We define and study exact, efficient representations of realization spaces of a natural class of underconstrained 2D Euclidean Distance constraint systems (Linkages or Frameworks) based on 1-dof Henneberg-I graphs. Each representation corresponds to a choice of parameters and yields a different parametrized configuration space. Our notion of efficiency is based on the algebraic complexities of sampling the configuration space and of obtaining a realization from the sample (parametrized) configuration. Significantly, we give purely combinatorial characterizations that capture (i) the class of graphs that have efficient configuration spaces and (ii) the possible choices of representation parameters that yield efficient configuration spaces for a given graph. Our results automatically yield an efficient algorithm for sampling realizations, without missing extreme or boundary realizations. In addition, our results formally show that our definition of efficient configuration space is robust and that our characterizations are tight. We choose the class of 1-dof Henneberg-I graphs in order to take the next step in a systematic and graded program of combinatorial characterizations of efficient configuration spaces. In particular, the results presented here are the first characterizations that go beyond graphs that have connected and convex configuration spaces.

REFERENCES

• 1: Ioannis Fudos , Christoph M. Hoffmann, A graph-constructive approach to solving systems of geometric constraints, ACM Transactions on Graphics (TOG), v.16 n.2, p.179-216, April 1997 [doi>10.1145/248210.248223]
• 2: H. Gao. Geometric Under-Constraints. Ph.D. thesis, University of Florida, 2008.
• 3: H. Gao, and M. Sitharam. Combinatorial Classification of 2D Underconstrained Sytems. Proceedings of the Seventh Asian Symposium on Computer Mathematics (ASCM 2005), Sung-il. Pae. and Hyungju. Park., Eds., 2005, Page 118--127.
• 4: H. Gao and M. Sitharam. Characterizing 1-Dof Henneberg-I graphs with efficient configuration spaces. arXiv: 0810.1997 {cs.CG}.
• 5: H. Gao and M. Sitharam. Characterizing 1-Dof Tree-Decomposable graphs with efficient configuration space. In preparation.
• 6: R. Joan-Arinyo , A. Soto-Riera , S. Vila-Marta , J. Vilaplana-Pastó, Transforming an under-constrained geometric constraint problem into a well-constrained one, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781616]
• 7: Hilderick A. van der Meiden, Willem F. Bronsvoort. A constructive approach to calculate parameter ranges for systems of geometric constraints. Computer-Aided Design, 38(4): 275--283, 2006
• 8: John C. Owen and Steve C. Power. The nonsolvability by radicals of generic 3-connected planar graphs. Transactions of AMS, 359(5): 2269--2303, 2006.
• 9: M. Sitharam. Graph based geometric constraint solving: problems, progress and directions. AMS-DIMACS volume on Computer Aided Design, D. Dutta, R. Janardhan, and M. Smid, Eds., 2005.
• 10: M. Sitharam and H. Gao. Characterizing graphs with convex and connected configuration spaces. arXiv: 0809.3935 {cs.CG}.
• 11: G. F. Zhang and X. S. Gao. Well-constrained Completion and Decomposition for Under-constrained Geometric Constraint Problems. International Journal of Computational Geometry and Applications, pages 461--478, 2006.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

Keywords:
Henneberg-I graph, algebraic complexity, combinatorial rigidity, computer aided design, configuration space, geometric constraints and reasoning, graph characterization, graph minor, linkage, mechanism, one degree of freedom (1-dof), quadratic or radical solvability, triangle-decomposable or tree-decomposable graph, underconstrained geometric constraint solving