Geometric constraints solving: some tracks

ABSTRACT

This paper presents some important issues and potential research tracks for Geometric Constraint Solving: the use of the simplicial Bernstein base to reduce the wrapping effect in interval methods, the computation of the dimension of the solution set with methods used to measure the dimension of fractals, the pitfalls of graph based decomposition methods, the alternative provided by linear algebra, the witness configuration method, the use of randomized provers to detect dependences between constraints, the study of incidence constraints, the search for intrinsic (coordinate-free) formulations and the need for formal specifications.

REFERENCES

• 1: Ait-Aoudia, S., Jegou, R., and Michelucci, D. 1993. Reduction of constraint systems. In Compugraphic, 83--92.
• 2: AUTODESK. 2005. DXF reference, July.
• 3: Michael Barnsley, Fractals everywhere, Academic Press Professional, Inc., San Diego, CA, 1988
• 4: Bellemain, F. 1992. Conception, réalisation et expérimentation d'un logiciel d'aide à l'enseignement de la géométrie: Cabri-géomètre. PhD thesis, Université Joseph Fourier - Grenoble 1.
• 5: Bonin, J. 2002. Introduction to matroid theory. The George Washington University.
• 6: Chou, S.-C., Schelter, W., and Yang, J.-G. 1987. Characteristic sets and grobner bases in geometry theorem proving. In Computer-Aided geometric reasoning, INRIA Workshop, Vol. I, 29--56.
• 7: S.-C. Chou, Mechanical geometry theorem proving, Kluwer Academic Publishers, Norwell, MA, 1987
• 8: Coxeter, H. 1987. Projective geometry. Springer-Verlag, Heidelberg.
• 9: Coxeter, H. 1999. The beauty of geometry. 12 essays. Dover publications.
• 10: Nello Cristianini , John Shawe-Taylor, An introduction to support Vector Machines: and other kernel-based learning methods, Cambridge University Press, New York, NY, 1999
• 11: Jean-François Dufourd , Pascal Mathis , Pascal Schreck, Formal resolution of geometrical constraint systems by assembling, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.271-284, May 14-16, 1997, Atlanta, Georgia, United States [doi>10.1145/267734.267804]
• 12: Jean-François Dufourd , Pascal Mathis , Pascal Schreck, Geometric construction by assembling solved subfigures, Artificial Intelligence, v.99 n.1, p.73-119, Feb. 1998 [doi>10.1016/S0004-3702(97)00070-2 ]
• 13: Cassiano Durand , Christophe M. Hoffmann, A systematic framework for solving geometric constraints analytically, Journal of Symbolic Computation, v.30 n.5, p.493-519, Nov. 2000 [doi>10.1006/jsco.2000.0392 ]
• 14: Cassiano Berenguer Durand , Christoph M. Hoffmann, Symbolic and numerical techniques for constraint solving, 1998
• 15: Gerald Farin, Curves and surfaces for computer aided geometric design: a practical guide, Academic Press Professional, Inc., San Diego, CA, 1988
• 16: Sebti Foufou , Dominique Michelucci , Jean-Paul Jurzak, Numerical decomposition of geometric constraints, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.143-151, June 13-15, 2005, Cambridge, Massachusetts [doi>10.1145/1060244.1060261]
• 17: Xiao-Shan Gao , Gui-Fang Zhang, Geometric constraint solving via C-tree decomposition, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781617]
• 18: Gao, X.-S., Hoffmann, C., and Yang, W. 2004. Solving spatial basic geometric constraint configurations with locus intersection. Computer Aided Design 36, 2, 111--122.
• 19: Garloff, J., and Smith, A. 2001. Solution of systems of polynomial equations by using bernstein expansion. Symbolic Algebraic Methods and Verification Methods, 87--97.
• 20: Garloff, J., and Smith, A. P. 2001. Investigation of a subdivision based algorithm for solving systems of polynomial equations. Journal of nonlinear analysis: Series A Theory and Methods 47, 1, 167--178.
• 21: Joseph A. Goguen, Modular algebraic specification of some basic geometrical constructions, Artificial Intelligence, v.37 n.1-3, p.123-153, Dec. 1988 [doi>10.1016/0004-3702(88)90052-5 ]
• 22: Bruce Hendrickson, Conditions for unique graph realizations, SIAM Journal on Computing, v.21 n.1, p.65-84, Feb. 1992 [doi>10.1137/0221008]
• 23: Hilbert, D. 1971. Les fondements de la géométrie, a french translation of Grunlagen de Geometrie, with discussions by P. Rossier. Dunod.
• 24: Hoffmann, C., and Joan-Arinyo, R. 2002. Handbook of Computer Aided Geometric Design. North-Holland, Amsterdam, ch. Parametric Modeling, 519--542.
• 25: Decomposition plans for geometric constraint systems, part I: performance measures for CAD, Journal of Symbolic Computation, v.31 n.4, p.367-408, April 1, 2001 [doi>10.1006/jsco.2000.0402 ]
• 26: Hoffmann, C., Sitharam, M., and Yuan, B. 2004. Making constraint solvers more usable: overconstraint problem. Computer-Aided Design 36, 2, 377--399.
• 27: Hu, C.-Y., Patrikalakis, N., and Ye, X. 1996. Robust Interval Solid Modelling. Part 1: Representations. Part 2: Boundary Evaluation. CAD 28, 10, 807--817, 819--830.
• 28: J. Graver, B. Servatius, H. S. 1993. Combinatorial Rigidity. Graduate Studies in Mathematics. American Mathematical Society.
• 29: 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]
• 30: Kortenkamp, U. 1999. Foundations of Dynamic Geometry. PhD thesis, Swiss Federal Institue of Technology, Zurich.
• 31: Lamure, H., and Michelucci, D. 1998. Qualitative study of geometric constraints. In Geometric Constraint Solving and Applications, Springer-Verlag.
• 32: Laurent, M. 2001. Matrix completion problems. The Encyclopedia of Optimization 3, Interior - M, 221--229.
• 33: Lesage, D., Léon, J.-C., and Serré, P. 2000. A declarative approach to a 2d variational modeler. In IDMME'00.
• 34: Mandelbrot, B. 1982. The Fractal Geometry of Nature. W.H. Freeman and Company, New York.
• 35: Michelucci, D., and Faudot, D. 2005. A reliable curves tracing method. IJCSNS 5, 10.
• 36: Michelucci, D., and Foufou, S. 2004. Using Cayley Menger determinants. In Proceedings of the 2004 ACM symposium on Solid modeling, 285--290.
• 37: Michelucci, D., and Foufou, S. 2006. Geometric constraint solving: the witness configuration method. To appear in Computer Aided Design, Elsevier.
• 38: Michelucci, D., and Schreck, P. 2004. Detecting induced incidences in the projective plane. In isiCAD Workshop.
• 39: Geraldine Morin , Ron Goldman, Analytic functions in computer-aided geometric design, 2002
• 40: Mourrain, B., Rouillier, F., and Roy, M.-F. 2004. Bernstein's basis and real root isolation. Tech. Rep. 5149, INRIA Rocquencourt.
• 41: Nataraj, P. S. V., and Kotecha, K. 2004. Global optimization with higher order inclusion function forms part 1: A combined taylor-bernstein form. Reliable Computing 10, 1, 27--44.
• 42: Neumaier, A. Cambridge, 2001. Introduction to Numerical Analysis. Cambridge Univ. Press.
• 43: 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]
• 44: Porta, J. M., Thomas, F., Ros, L., and Torras, C. 2003. A branch and prune algorithm for solving systems of distance constraints. In Proceedings of the 2003 IEEE International Conference on Robotics & Automation.
• 45: Richter-Gebert, J. 1996. Realization Spaces of Polytopes. Lecture Notes in Mathematics 1643, Springer.
• 46: Schramm, E., and Schreck, P. 2003. Solving geometric constraints invariant modulo the similarity group. In International Workshop on Computer Graphics and Geometric Modeling, CGGM'2003, Springer-Verlag, Montréal, LNCS Series.
• 47: Robustness in CAD Geometric Constructions, Proceedings of the Fifth International Conference on Information Visualisation, p.111, July 25-27, 2001
• 48: Serré, P., Clément, A., and Riviére, A. 1999. Global consistency of dimensioning and tolerancing. ISBN 0-7923-5654-3. Kluwer Academic Publishers, March, 1--26.
• 49: Serré, P., Clément, A., and Riviére, A. 2002. Formal definition of tolerancing in CAD and metrology. In Integrated Design an Manufacturing in Mechanical Engineering. Proc. Third ID-MME Conference, Montreal, Canada, May 2000, Kluwer Academic Publishers, 211--218.
• 50: Serré, P., Clément, A., and Riviére, A. 2003. Analysis of functional geometrical specification. In Geometric Product Specification and Verification: Integration of functionality. Kluwer Academic Publishers, 115--125.
• 51: Serré, P. 2000. Cohérence de la spécification d'un objet de l'espace euclidien à n dimensions. PhD thesis, Ecole Centrale de Paris.
• 52: Evan C. Sherbrooke , Nicholas M. Patrikalakis, Computation of the solutions of nonlinear polynomial systems, Computer Aided Geometric Design, v.10 n.5, p.379-405, Oct. 1993 [doi>10.1016/0167-8396(93)90019-Y ]
• 53: Sitharam, M., Oung, J.-J., Zhou, Y., and Arbree, A. 2006. Geometric constraints within feature hierarchies. Computer-Aided Design 38, 2, 22--38.
• 54: Bernd Sturmfels, Algorithms in invariant theory, Springer-Verlag New York, Inc., New York, NY, 1993
• 55: Wintz, J., Mathis, P., and Schreck, P. 2005. A metalanguage for geometric constraints description. In CAD Conference (presentation only, available at http://axis.u-strasbg.fr/~schreck/Publis/gcml.pdf).
• 56: J. Van Leeuwen, Handbook of Theoretical Computer Science, Elsevier Science Inc., New York, NY, 1990
• 57: Yang, L. 2002. Distance coordinates used in geometric constraint solving. In Proc. 4th Intl. Workshop on Automated Deduction in Geometry.
• 58: Gui-Fang Zhang , Xiao-Shan Gao, Spatial geometric constraint solving based on k-connected graph decomposition, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141510]

INDEX TERMS

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

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

Keywords:
bernstein base, decomposition, geometric constraints solving, incidence constraint, projective geometry, randomized prover, rigidity theory, witness configuration