×

A systematic framework for solving geometric constraints analytically. (English) Zbl 0967.65029

A systematic framework is presented for solving algebraic equations arising in geometric constraint solving. The approach combines geometric reasoning, symbolic reduction, and homotopy continuation. The literature concerning the methods which may be used to numerically solve the nonlinear systems which are derived are also thoroughly surveyed. Among the methods discussed are the homotopy methods, Gröbner basis methods and elimination methods.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
65H10 Numerical computation of solutions to systems of equations
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aldefeld, B., Variation of geometries based on a geometric-reasoning method, Comput. Aided Des., 20, 117-126 (1988) · Zbl 0656.65017
[2] Allgower, E. L.; Georg, K., Numerical Continuation Methods. An Introduction (1990), Springer-Verlag: Springer-Verlag New York · Zbl 0717.65030
[3] Allgower, E. L.; Georg, K., Continuation and path following, Acta Numerica, 2, 1-64 (1993) · Zbl 0792.65034
[4] Allgower, E. L.; Georg, K., Numerical path following, (Ciarlet, P. G.; Lions, J. L., Techniques of Scientific Computing (Part 2), volume 5 of Handbook of Numerical Analysis (1997), North-Holland: North-Holland Amsterdam), 3-203
[5] Betke, U., Mixed volumes of polytopes, Arch. Math., 58, 388-391 (1992) · Zbl 0766.52006
[6] Bonnesen, T.; Fenchel, W., Theory of Convex Bodies (1987), BCS Associates · Zbl 0628.52001
[7] Borning, A. H., The programming language aspects of ThingLab, a constraint oriented simulation laboratory, ACM TOPLAS, 3, 353-387 (1981)
[8] Bouma, W.; Fudos, I.; Hoffmann, C. M.; Cai, J.; Paige, R., A geometric constraint solver, Comput. Aided Des., 27, 485-501 (1995) · Zbl 0960.68721
[9] B. D. Brüderlin, 1987; B. D. Brüderlin, 1987
[10] B. Buchberger, 1965; B. Buchberger, 1965
[11] Buchberger, B., Gröbner bases: An algorithmic method in polynomial ideal theory, (Bose, N. K., Recent Trends in Multidimensional Systems Theory (1985), D. Reidel: D. Reidel Dordrecht), 184-232 · Zbl 0587.13009
[12] Chou, S. C., An introduction to Wu’s method for mechanical theorem proving in geometry, J. Autom. Reasoning, 4, 237-267 (1988) · Zbl 0715.03005
[13] Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties and Algorithms (1992), Springer-Verlag: Springer-Verlag New York
[14] Crippen, G. M.; Havel, T. F., Distance Geometry and Molecular Conformation (1988), Research Studies Press: Research Studies Press Somerset, England · Zbl 1066.51500
[15] D-Cubed, The Dimensional Constraint Manager (1994)
[16] Dennis, J. E.; Schnabel, R. B., Numerical Methods of Unconstrained Optimization and Nonlinear Equations (1983), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0579.65058
[17] C. Durand, 1998; C. Durand, 1998
[18] C. Durand, C. M. Hoffmann, 1998, Department of Computer Sciences, Purdue University, West Lafayette, IN, U.S.A; C. Durand, C. M. Hoffmann, 1998, Department of Computer Sciences, Purdue University, West Lafayette, IN, U.S.A
[19] Dyer, M.; Gritzmann, P.; Hufnagel, A., On the complexity of computing mixed volumes, SIAM J. Comput., 17, 356-400 (1998) · Zbl 0909.68193
[20] Emiris, I. Z.; Canny, J. F., Efficient incremental algorithm for the sparse resultant and the mixed volume, J. Symb. Comput., 20, 117-149 (1995) · Zbl 0843.68036
[21] I. Z. Emiris, B. Mourrain, 1996, INRIA; I. Z. Emiris, B. Mourrain, 1996, INRIA
[22] I. Z. Emiris, J. Verschelde, 1997, INRIA; I. Z. Emiris, J. Verschelde, 1997, INRIA
[23] I. Fudos, 1995; I. Fudos, 1995
[24] I. Fudos, C. M. Hoffmann, 1993, Department of Computer Sciences, Purdue University, West Lafayette, IN, U.S.A.; I. Fudos, C. M. Hoffmann, 1993, Department of Computer Sciences, Purdue University, West Lafayette, IN, U.S.A.
[25] Fudos, I.; Hoffmann, C. M., Constraint-based parametric conics for CAD, Comput. Aided Des., 28, 91-100 (1996)
[26] Gelfand, I. M., Discriminants, Resultants, and Multidimensional Determinants (1994), Birkhauser: Birkhauser Basel · Zbl 0827.14036
[27] C. M. Henneberg; C. M. Henneberg
[28] Hoffmann, C. M., Solid and Geometric Modeling (1989), Morgan Kaufmann: Morgan Kaufmann California, U.S.A
[29] Hoffmann, C. M.; Joan-Arinyo, R., Symbolic constraints in constructive geometry, J. Symb. Comput., 23, 287-300 (1997) · Zbl 0878.68135
[30] Hoffmann, C. M.; Lomonosov, A.; Sitharam, M., Finding dense subgraphs of constraint graphs, (Smolka, G., Constraint Programming ’97 (1997), Springer-Verlag: Springer-Verlag New York), 463-478
[31] Hoffmann, C. M.; Lomonosov, A.; Sitharam, M., (Smolka, G., Finding solvable subsets of constraint graphs (1997), Springer: Springer New York), 463-477
[32] Hoffmann, C. M.; Vermeer, P. J., Geometric constraint solving in \(R^2\) and \(R^3\), Computing in Euclidean Geometry (1994), World Scientific Publishing: World Scientific Publishing Singapore
[33] C. M. Hoffmann, P. J. Vermeer, Proceedings of the Computational Kinematics Workshop, Nice, France, September 1995, 1995, ACM, New York; C. M. Hoffmann, P. J. Vermeer, Proceedings of the Computational Kinematics Workshop, Nice, France, September 1995, 1995, ACM, New York
[34] B. Huber, 1996; B. Huber, 1996
[35] Huber, B.; Sturmfels, B., A polyhedral method for solving sparse polynomial systems, Math. Comput., 64, 1541-1555 (October 1995)
[36] Huber, B.; Sturmfels, B., Bernstein’s theorem in affine space, Discrete Comput. Geom., 17, 137-141 (1997) · Zbl 0891.65055
[37] Joan-Arinyo, R.; Soto, A., A correct rule-based geometric constraint solver, Comput. Graph., 21, 599-609 (1997)
[38] Joan-Arinyo, R.; Soto, A., A ruler-and-compass geometric constraint solver, (Pratt, M. J.; Sriram, R. D.; Wozny, M. J., Product Modeling for Computer Integrated Design and Manufacture (1997), Chapman and Hall: Chapman and Hall London), 384-393
[39] Kalkbrener, M., A generalized Euclidean algorithm for computing triangular representations of algebraic varieties, J. Symb. Comput., 15, 143-167 (1993) · Zbl 0783.14039
[40] Khovanskii, A. G., Newton polyhedra and toroidal varieties, Funct. Anal. Appl., 11, 289-296 (1977) · Zbl 0445.14019
[41] Khovanskii, A. G., Newton polyhedra and the genus of complete intersections, Funktsional’nyi Analiz i Ego Prilozheniya, 12, 51-61 (1978)
[42] Kondo, K., Algebraic method for manipulation of dimensional relationships in geometric models, Comput. Aided Des., 24, 141-147 (1992) · Zbl 0752.65106
[43] Kushnirenko, A. G., A Newton polytope and the number of solutions of a system of k equations in k unknowns, Uspekhi Matematicheskikh Nauk., 30, 266-267 (1975)
[44] Lahaye, E., Une méthode de resolution d’une categorie d’equations transcendantes, Comptes Rendus Séances Acad. Sci., 198, 1840-1842 (1934) · JFM 60.0259.03
[45] Laman, G., On graphs and the rigidity of plane skeletal structures, J. Eng. Math., 4, 331-340 (1970) · Zbl 0213.51903
[46] Lamure, H.; Michelucci, D., Solving geometric constraints by homotopy, Third Symposium on Solid Modeling and its Applications, Salt Lake City, UT (1995), ACM: ACM New York, p. 263-269
[47] Lazard, D., A new method for solving algebraic systems of positive dimension, Discrete Appl. Math., 33, 147-160 (1991) · Zbl 0753.13013
[48] Lazard, D., On theories of triangular sets, J. Symb. Comput., 28, 105-124 (1999) · Zbl 0943.12003
[49] Li, T. Y., Numerical solutions of multivariate polynomial systems by homotopy continuation methods, Acta Numerica, 6, 399-436 (1997) · Zbl 0886.65054
[50] Li, T. Y.; Sauer, T.; Yorke, J. A., The Cheater’s homotopy: an efficient procedure for solving system of polynomial equations, SIAM J. Numer. Anal., 26, 1241-1251 (1989) · Zbl 0689.65032
[51] Manocha, D., Efficient algorithms for multipolynomial resultant, Comput. J. Special issue on Quantifier Elimination., 36, 485-496 (1993) · Zbl 0780.68076
[52] Manocha, D.; Canny, J., Multipolynomial resultant algorithms, J. Symb. Comput., 15, 99-122 (1993) · Zbl 0778.13023
[53] Morgan, A. P., A homotopy for solving polynomial systems, Appl. Math. Comput., 18, 87-92 (1986) · Zbl 0597.65046
[54] Morgan, A. P., A transformation to avoid solutions at infinity for polynomial systems, Appl. Math. Comput., 18, 77-86 (1986) · Zbl 0597.65045
[55] Morgan, A., Solving Polynomial Systems using Continuation for Engineering and Scientific Problems (1987), Prentice-Hall: Prentice-Hall New Jersey · Zbl 0733.65031
[56] Morgan, A. P., Polynomial continuation and its relationship to the symbolic reduction of polynomial systems, (Donald, B. R.; Kapur, D.; Mundy, J. L., Symbolic and Numerical Computation for Artificial Inteligence (1992), Academic Press: Academic Press San Diego)
[57] Morgan, A. P.; Sommese, A. J., Coefficient-parameter polynomial continuation, Appl. Math. Comput., 29, 123-160 (1989) · Zbl 0664.65049
[58] Nanua, P.; Waldron, K. J.; Murthy, V., Direct kinematic solution of a Stewart platform, IEEE Trans. Robot. Autom., 6, 438-443 (1990)
[59] Ortega, J.; Rheinboldt, W., Iterative Solution of Nonlinear Equations in Several Variables (1970), Academic Press: Academic Press San Diego · Zbl 0241.65046
[60] Owen, J., Algebraic solution for geometry from dimensional constraints, ACM Symposium on the Foundations of Solid Modeling, Austin, TX (1991), ACM: ACM New York, p. 397-407
[61] Patrikalakis, N. M., Surface-to-surface intersections, IEEE Comput. Graph. Appl., 13, 89-95 (1992)
[62] Peitgen, H. O.; Ritcher, P. H., The Beauty of Fractals, Images of Complex Dynamical Systems (1986), Springer-Verlag: Springer-Verlag New York · Zbl 0601.58003
[63] Ritt, J. F., Differential Equations from the Algebraic Standpoint (1932), American Mathematical Society: American Mathematical Society Providence, R.I., U.S.A · Zbl 0005.39404
[64] Ritt, J. F., Differential Algebra (1950), American Mathematical Society: American Mathematical Society Providence, R.I., U.S.A · Zbl 0037.18501
[65] Rojas, J. M., Solving degenerate sparse polynomial systems faster, J. Symb. Comput., 28, 155-186 (1999) · Zbl 0943.65060
[66] Schneider, R., Convex Bodies (1993), Cambridge University Press: Cambridge University Press Cambridge
[67] T. W. Sederberg, August 1983; T. W. Sederberg, August 1983
[68] Stoer, J.; Bulirsch, R., Introduction to Numerical Analysis (1993), Springer-Verlag: Springer-Verlag New York · Zbl 0771.65002
[69] B. Sturmfels, Lecture Notes at the AMS Short Course on Applications of Computational Algebraic Geometry, San Diego, January 1997; B. Sturmfels, Lecture Notes at the AMS Short Course on Applications of Computational Algebraic Geometry, San Diego, January 1997
[70] Verroust, A.; Schonek, F.; Roller, D., Rule-oriented method for parametrized computer-aided design, Comput. Aided Des., 24, 531-540 (1992) · Zbl 0760.65017
[71] J. Verschelde, 1996; J. Verschelde, 1996
[72] J. Verschelde; J. Verschelde
[73] J. Verschelde, 1997, Department of Computer Science, Katholieke Universiteit Leuven; J. Verschelde, 1997, Department of Computer Science, Katholieke Universiteit Leuven
[74] J. Verschelde; J. Verschelde
[75] Verschelde, J.; Gatermann, K.; Cools, R., Mixed-volume computation by dynamic lifting applied to polynomial system solving, Discrete Comput. Geom., 16, 69-112 (1996) · Zbl 0854.68111
[76] Wampler, C. W.; Morgan, A. P.; Sommese, A. J., Numerical continuation methods for solving systems arising in kinematics, J. Mech. Des., 112, 59-68 (1990)
[77] Wang, D., On Wu’s Method for Solving Systems of Algebraic Equations (1991), Johannes Kepler University: Johannes Kepler University Austria
[78] Wang, D., Decomposing polynomial systems into simple systems, J. Symb. Comput., 25, 295-314 (1998) · Zbl 0913.12008
[79] Wu, W., Basic principles of mechanical theorem proving in elementary geometries, J. Autom. Reasoning, 2, 221-252 (1986) · Zbl 0642.68163
[80] Wu, W., Mechanical Theorem Proving in Geometries: Basic Principles (1994), Springer-Verlag: Springer-Verlag New York
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.