Geometric computations with algebraic varieties of bounded degree

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Geometric computations with algebraic varieties of bounded degree

Full text

Pdf (715 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the sixth annual symposium on Computational geometry table of contents

Berkley, California, United States

Pages: 148 - 156

Year of Publication: 1990

ISBN:0-89791-362-0

Author

Chanderjit L. Bajaj

Department of Computer Science, Purdue University, West Lafayette, IN

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 14, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/98524.98557 What is a DOI?

ABSTRACT

The set of solutions to a collection of polynomial equations is referred to as an algebraic set. An algebraic set that cannot be represented as the union of two other distinct algebraic sets, neither containing the other, is said to be irreducible. An irreducible algebraic set is also known as an algebraic variety. This paper deals with geometric computations with algebraic varieties. The main results are algorithms to (1) compute the degree of an algebraic variety, (2) compute the rational parametric equations (a rational map from points on a hyperplane) for implicitly defined algebraic varieties of degrees two and three. These results are based on sub-algorithms using multi-polynomial resultants and multi-polynomial remainder sequences for constructing a one-to-one projection map of an algebraic variety to a hypersurface of equal dimension, as well as, an inverse rational map from the hypersurface to the algebraic variety. These geometric computations arise naturally in geometric modeling, computer aided design, computer graphics, and motion planning, and have been used in the past for special cases of algebraic varieties, i.e. algebraic curves and surfaces.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Abhyankar, S. (1988), "Good Points ofa Hypersurface," Advances in Mathematics, 68, 2, 87 - 256.
	2	S. S. Abhyankar , C. Bajaj, Automatic parameterization of rational curves and surfaces 1: conics and conicoids, Computer-Aided Design, v.19 n.1, p.11-14, Jan./Feb. 1987 [doi>10.1016/0010-4485(87)90147-3]
	3	S. S. Abhyanker , C. Bajaj, Automatic parametrization of rational curves and surfaces II: cubics and cubicoids, Computer-Aided Design, v.19 n.9, p.499-502, Nov. 1987 [doi>10.1016/0010-4485(87)90235-1]
	4	Shreeram S. Abhyankar , Chandrajit L. Bajaj, Computations with Algebraic Curves, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.274-284, July 04-08, 1988
	5	Chandrajit L. Bajaj, Geometric Modeling with Algebraic Surfaces, Proceedings of the 3rd IMA Conference on the Mathematics of Surfaces, p.3-48, September 19-21, 1988
	6	Bajaj, C., (1989b), "Local Parameterization, Implicitization and Inversion of Real Algebraic Curves", Computer Science Technical Report, Purdue University, CSD-TR-863 and CAPO-89- 9. Proc. of the AAECC-7 Conference, (1989), Toulouse, France.
	7	Chanderjit L. Bajaj, Rational hypersurface display, Proceedings of the 1990 symposium on Interactive 3D graphics, p.117-127, February 1990, Snowbird, Utah, United States
	8	C. Bajaj , J. Canny , R. Garrity , J. Warren, Factoring rational polynomials over the complexes, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.81-90, July 17-19, 1989, Portland, Oregon, United States [doi>10.1145/74540.74551]
	9	C. L. Bajaj , C. M. Hoffman , R. E. Lynch , J. E. H. Hopcroft, Tracing surface intersections, Computer Aided Geometric Design, v.5 n.4, p.285-307, Nov. 1988 [doi>10.1016/0167-8396(88)90010-6]
	10	Chandrajit L. Bajaj , Andrew V. Royappa, The GANITH algebraic geometry toolkit, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.268-269, April 10-12, 1990
	11	Buchberger, B., (1985) "Grhbner Bases: An Algorithmic Method in Polynomial Ideal Theory," Multidimensional Systems Theory, Chapter 6, N. Bose (eds). Reidel Publishing Co.
	12	John Canny, Some algebraic and geometric computations in PSPACE, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.460-469, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62257]
	13	John F. Canny, Generalized Characteristic Polynomials, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.293-299, July 04-08, 1988
	14	Canny, 3. F., Kaltofen, E., and Lakshman, Y. (1989) "Solving Systems of Polynomial Equations Faster", Technical Report No. 89-14, Dept. of Computer Science, Rensselaer Polytechnic institute
	15	Cayley, A. (1848), "On the Theory of Elimination," Cambridge and Dublin Mathematics Journal, Vol. III, pp. 116-120.
	16	Chistov, A., and Grigoryev, D. (1983), "Subexponential-Time Solving Systems of Algebraic Equations I", Steklov Institute, LOMI preprint E-9-83.
	17	James H. Davenport, The computerization of algebraic geometry, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.119-133, June 01, 1979
	18	Fulton, W. (1984) Intersection Theory, Springer- Verlag.
	19	Thomas Garrity , Joe Warren, On computing the intersection of a pair of algebraic surfaces, Computer Aided Geometric Design, v.6 n.2, p.137-153, May 1989 [doi>10.1016/0167-8396(89)90017-4]
	20	Marc Giusti, Some Effectivity Problems in Polynomial Ideal Theory, Proceedings of the International Symposium on Symbolic and Algebraic Computation, p.159-171, July 09-11, 1984
	21	Hartshorne, R. (1977), Algebraic Geometry, Springer-Verlag.
	22	Hensel, K., (1908) Theorie der Algebraischen Zahlen, Teubner, Leipzig.
	23	Ho, C., and Yap, C. K. (1987)"Polynomial Remainder Sequences and Theory of Subresuitants", Technical Report No. 319, Robotics Report No. 119, Courant institute of Mathematical Sciences, New York University.
	24	Hopcroft, J., and Kraft, D., (1985) The Challenge of Robotics for Computer Science, Advances in Robotics: Algorithmic and Geometric Aspects of Robotics, eds, J. Schwartz, and C. Yap, vol 1, 7- 42.
	25	John K. Johnstone , Chanderjit L. Bajaj, Sorting points along an algebraic curve, SIAM Journal on Computing, v.19 n.5, p.925-967, Oct. 1990 [doi>10.1137/0219065]
	26	Konig, J., (1903) Einleitung in die Allgemeine Theorie der A lgebriaschen Grossen, Leipzig.
	27	Kroneeker, L., (1882) Grundzuge ether Arithmetisehen Theorie der Algebraisehen Grossen, Crelle Journal, 92, 1-122.
	28	Krull, W., (1952-1959) Elementare und Klassische Algebra vorn Moderne Standpunkt, Parts I and II, De Gruyter, Berlin.
	29	Levin, J., (1979) Mathematical Models for Determining the Intersections of Quadric Surfaces, Computer Graphics and Image Processing, 11, 73- 87.
	30	Daniel Lazard, Gröbner-Bases, Gaussian elimination and resolution of systems of algebraic equations, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.146-156, March 28-30, 1983
	31	Loos, R., (1983) "Generalized Polynomial Remainder Sequences", Computer Algebra, Symbolic and Algebraic Computation, 115-137, Buchberger, Collins, Loos, Albrecht, eds., Second Edition, Wien, New York.
	32	Macaulay, F. (1902), "Some Formulae in Elimination," Proc. London Math. Soc., Vol. 35, pp. 3-27.
	33	Mayr, E. and Meyer, i. (1982), "The Complexity of the Word Problems for Commutative Semigroups and Polynomial Ideals," Advances in Mathematics, Vol. 46, pp. 305-329.
	34	Ferdinando Mora , H. Michael Möller, The computation of the Hilbert function, Proceedings of the European Computer Algebra Conference on Computer Algebra, p.157-167, March 28-30, 1983
	35	Ocken, Schwartz, J., Sharir, M., (1986) Precise Implementation of CAD Primitives Using Rational Parameterization of Standard Surfaces, Planning, Geometry, and Complexity of Robot Motion,ed., Schwartz, Sharir, Hopcroft, Chap 10, 245-266.
	36	Renegar, J. (1989) "On the Computational Complexity and Geometry of the First-Order Theory of Reals (Parts I,II, III)", Technical Report No. 853, 854, 856, School of Operations Research and Industrial Engineering, Cornell University
	37	Salmon, G., (1885) Lessons Introductory to the Modern Higher Algebra, Chelsea Publishing Company, NY.
	38	Semple, J., and Roth, L., (1949) Introduction to Algebraic Geometry, Clarendon Press, Oxford.
	39	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	40	Schwartz, J., and Sharir, M., (1983) On the Piano Movers' Problem: II, General Techniques for Computing Topological Properties of Real Algebraic Manifolds, Advances in Applied Mathematics, 4, 298- 351.
	41	T. W. Sederberg , J. P. Snively, Parametrization of cubic algebraic surfaces, Proceedings on Mathematics of surfaces II, p.299-319, October 1987, Cardiff, United Kingdom
	42	Wilson, P.M.H. (1987), "Towards Birational Classification of Algebraic Varieties," Bull. London Math Soc., Vol. 19, pp. 1-48.
	43	Zariski, O. and Samuel, P. (1958), Commutative Algebra (Vol.I, II), Springer Verlag.

CITED BY 2

	Chandrajit L. Bajaj , Robert L. Holt , Arun N. Netravali, Rational parametrizations of nonsingular real cubic surfaces, ACM Transactions on Graphics (TOG), v.17 n.1, p.1-31, Jan. 1998
	Chandrajit L. Bajaj , Andrew Royappa, Triangulation and display of rational parametric surfaces, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.