Revisiting decomposition analysis of geometric constraint graphs

ABSTRACT

Geometric problems defined by constraints can be represented by geometric constraint graphs whose nodes are geometric elements and whose arcs represent geometric constraints. Reduction and decomposition are techniques commonly used to analyze geometric constraint graphs in geometric constraint solving. In this paper we first introduce the concept of deficit of a constraint graph. Then we give a new formalization of the decomposition algorithm due to Owen. This new formalization is based on preserving the deficit rather than on computing triconnected components of the graph and is simpler. Finally we apply tree decompositions to prove that the class of problems solved by the formalizations studied here and other formalizations reported in the literature is the same.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Gary Chartrand , Linda Lesniak, Graphs & digraphs (2nd ed.), Wadsworth Publ. Co., Belmont, CA, 1986
• 3: Cassiano Berenguer Durand , Christoph M. Hoffmann, Symbolic and numerical techniques for constraint solving, 1998
• 4: Ioannis Fudos , Christoph M. Hoffmann, Constraint solving for computer-aided design, 1995
• 5: I. Fudos and C.M. Hoffmann. Correctness proof of a geometric constraint solver. International Journal of Computational Geometry and Applications, 6(4):405--420, 1996
• 6: 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]
• 7: C.M. Hoffmann, A. Lomonosov, and M. Sitharam. Geometric constraint decomposition. In B. Bruderlin and D. Roller, editors, Geometric Constraint Solving and Applications, pages 171--195. Springer, Berlin, 1998
• 8: J. E. Hopcroft and R. E. Tarjan. Dividing a graph into triconnected components. Technical report, Computer Science Department. Cornell University, Ithaca, NY. USA, February 1974. New revision of TR 72--140
• 9: R. Joan-Arinyo , A. Soto-Riera, Combining constructive and equational geometric constraint-solving techniques, ACM Transactions on Graphics (TOG), v.18 n.1, p.35-55, Jan. 1999 [doi>10.1145/300776.300780]
• 10: Robert Joan-Arinyo , Antoni Soto-Riera , Sebastià Vila-Marta , Josep Vilaplana, On the Domain of Constructive Geometric Constraint Solving Techniques, Proceedings of the 17th Spring conference on Computer graphics, p.49, April 25-28, 2001
• 11: G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 4(4):331--340, October 1970
• 12: Zohar Manna , Richard Waldinger, The deductive foundations of computer programming: a one-volume version of “the logical basis for computer programming”, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 13: N. Mata. Solving incidence and tangency constraints in 2D. Technical Report LSI-97-3R, Department LSI, Universitat Politecnica de Catalunya, 1997
• 14: Gary L. Miller and Vijaya Ramachandran. A new graph triconnectivity algorithm and its parallelization. Combinatorica, 12:53--76, 1992
• 15: J. C. Owen, Algebraic solution for geometry from dimensional constraints, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.397-407, June 05-07, 1991, Austin, Texas, United States [doi>10.1145/112515.112573]
• 16: Philip Todd, A k-tree generalization that characterized consistency of dimensioned engineering drawings, SIAM Journal on Discrete Mathematics, v.2 n.2, p.255-261, May 1989 [doi>10.1137/0402022]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
constraint solving, geometric constraints, graph-based constraint solving