Fast and exact geometric analysis of real algebraic plane curves

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast and exact geometric analysis of real algebraic plane curves

Full text

Pdf (357 KB)

Source

International Conference on Symbolic and Algebraic Computation archive
Proceedings of the 2007 international symposium on Symbolic and algebraic computation table of contents

Waterloo, Ontario, Canada

SESSION: Contributed papers table of contents

Pages: 151 - 158

Year of Publication: 2007

ISBN:978-1-59593-743-8

Authors

Arno Eigenwillig	Max-Planck-Institut für Informatik
Michael Kerber	Max-Planck-Institut für Informatik
Nicola Wolpert	Hochschule für Technik

Sponsors

ACM: Association for Computing Machinery
SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 30, Citation Count: 16

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/1277548.1277570 What is a DOI?

ABSTRACT

An algorithm is presented for the geometric analysis of an algebraic curve f(x, y) = 0 in the real affine plane. It computes a cylindrical algebraic decomposition (CAD) of the plane, augmented with adjacency information. The adjacency information describes the curve's topology by a topologically equivalent planar graph. The numerical data in the CAD gives an embedding of the graph.

The algorithm is designed to provide the exact result for all inputs but to perform only few symbolic operations for the sake of efficiency. In particular, the roots of f(∝, y) at a critical x-coordinate .

The algorithm is implemented as C++ library AlciX in the EXACUS project. Running time comparisons with top by Gonzalez-Vega and Necula (2002), and with cad2d by Brown demonstrate its efficiency.

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	J. Abbott: "Quadratic Interval Refinement for Real Roots". URL http://www.dima.unige.it/~abbott/. Poster presented at the 2006 Int. Symp. on Symb. and Alg. Comp. (ISSAC 2006).
	2	Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition I: the basic algorithm, SIAM Journal on Computing, v.13 n.4, p.865-877, Nov. 1984 [doi>10.1137/0213054]
	3	Dennis S. Arnon , George E. Collins , Scott McCallum, Cylindrical algebraic decomposition II: an adjacency algorithm for the plane, SIAM Journal on Computing, v.13 n.4, p.878-889, Nov. 1984 [doi>10.1137/0213055]
	4	Saugata Basu , Richard Pollack , Marie-Françoise Roy, Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
	5	E. Berberich, A. Eigenwillig, M. Hemmer, S. Hert, L. Kettner, K. Mehlhorn, J. Reichel, S. Schmitt, E. Schömer, N. Wolpert: "EXACUS: Efficient and exact algorithms for curves and surfaces". In: Proc. of the 13th Ann. European Symp. on Alg. (ESA 2005), LNCS, vol. 3669. Springer, 2005 155--166.
	6	C. W. Brown: "Constructing Cylindrical Algebraic Decompositions of the Plane Quickly", 2002. URL http://www.cs.usna.edu/~wcbrown/. Unpublished.
	7	George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
	8	George E. Collins , Alkiviadis G. Akritas, Polynomial real root isolation using Descarte's rule of signs, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.272-275, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806346]
	9	George E. Collins , Jeremy R. Johnson , Werner Krandick, Interval arithmetic in cylindrical algebraic decomposition, Journal of Symbolic Computation, v.34 n.2, p.145-157, August 2002 [doi>10.1006/jsco.2002.0547]
	10	L. Ducos: "Optimizations of the Subresultant Algorithm". J. Pure Appl. Alg. 145 (2000) 149--163.
	11	Arno Eigenwillig, Short Communication: On multiple roots in Descartes' Rule and their distance to roots of higher derivatives, Journal of Computational and Applied Mathematics, v.200 n.1, p.226-230, March, 2007 [doi>10.1016/j.cam.2005.12.016]
	12	A. Eigenwillig, L. Kettner, W. Krandick, K. Mehlhorn, S. Schmitt, N. Wolpert: "A Descartes Algorithm for Polynomials with Bit-Stream Coefficients". In: 8th Int. Workshop on Comp. Alg. in Scient. Comp. (CASC 2005), LNCS, vol. 3718, 2005 138--149.
	13	Arno Eigenwillig , Vikram Sharma , Chee K. Yap, Almost tight recursion tree bounds for the Descartes method, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145786]
	14	Laureano González-Vega , M'Hammed El Kahoui, An improved upper complexity bound for the topology computation of a real algebraic plane curve, Journal of Complexity, v.12 n.4, p.527-544, Dec. 1996 [doi>10.1006/jcom.1996.0032]
	15	Laureano Gonzalez-Vega , Ioana Necula, Efficient topology determination of implicitly defined algebraic plane curves, Computer Aided Geometric Design, v.19 n.9, p.719-743, December 2002 [doi>10.1016/S0167-8396(02)00167-X]
	16	L. Gonzalez-Vega, T. Recio, H. Lombardi, M. -F. Roy: "Sturm-Habicht Sequences, Determinants and Real Roots of Univariate Polynomials". In: B. Caviness, J. Johnson (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition, 300--316. Springer, 1998.
	17	Hoon Hong, An efficient method for analyzing the topology of plane real algebraic curves, Mathematics and Computers in Simulation, v.42 n.4-6, p.571-582, Nov. 1996
	18	J. R. Johnson: "Algorithms for polynomial real root isolation". In: B. F. Caviness, J. R. Johnson (eds.) Quantifier Elimination and Cylindrical Algebraic Decomposition, 269--299. Springer, 1998.
	19	Jeremy R. Johnson , Werner Krandick , Kevin Lynch , David G. Richardson , Anatole D. Ruslanov, High-performance implementations of the Descartes method, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145797]
	20	M. Kerber: Analysis of Real Algebraic Plane Curves. Master's thesis, Universität des Saarlandes, Saarbrücken, Germany, 2006.
	21	W. Krandick, K. Mehlhorn: "New Bounds for the Descartes Method". J. Symb. Comp. 41 (2006) 49--66.
	22	Scott McCallum, Factors of iterated resultants and discriminants, Journal of Symbolic Computation, v.27 n.4, p.367-385, April 1999 [doi>10.1006/jsco.1998.0257]
	23	Fabrice Rouillier , Paul Zimmermann, Efficient isolation of polynomial's real roots, Journal of Computational and Applied Mathematics, v.162 n.1, p.33-50, 1 January 2004 [doi>10.1016/j.cam.2003.08.015]
	24	Raimund Seidel , Nicola Wolpert, On the exact computation of the topology of real algebraic curves, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064111]
	25	A. Strzebonski: "Cylindrical Algebraic Decomposition using validated numerics". J. Symb. Comp. 41 (2006) 1021--1038.

CITED BY 16

	Eric Berberich , Michael Kerber , Michael Sagraloff, Exact geometric-topological analysis of algebraic surfaces, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Pavel Emeliyanenko , Michael Kerber, Visualizing and exploring planar algebraic arrangements: a web application, Proceedings of the twenty-fourth annual symposium on Computational geometry, June 09-11, 2008, College Park, MD, USA
	Eric Berberich , Michael Kerber, Exact arrangements on tori and Dupin cyclides, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York
	Arno Eigenwillig , Michael Kerber, Exact and efficient 2D-arrangements of arbitrary algebraic curves, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.122-131, January 20-22, 2008, San Francisco, California
	Eric Berberich , Michael Sagraloff, A generic and flexible framework for the geometrical and topological analysis of (algebraic) surfaces, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York
	Diatta Niang Daouda , Bernard Mourrain , Olivier Ruatta, On the computation of the topology of a non-reduced implicit space curve, Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, July 20-23, 2008, Linz/Hagenberg, Austria
	Mhammed El Kahoui, Topology of real algebraic space curves, Journal of Symbolic Computation, v.43 n.4, p.235-258, April, 2008
	D. A. Aruliah , Robert M. Corless , Azar Shakoori , Laureano Gonzalez-Vega , Ignacio F. Rua, Computing the topology of a real algebraic plane curve whose equation is not directly available, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Dimitrios I. Diochnos , Ioannis Z. Emiris , Elias P. Tsigaridas, On the complexity of real solving bivariate systems, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Jorge Caravantes , Laureano Gonzalez-Vega, Improving the topology computation of an arrangement of cubics, Computational Geometry: Theory and Applications, v.41 n.3, p.206-218, November, 2008
	Eric Berberich , Michael Sagraloff, A generic and flexible framework for the geometrical and topological analysis of (algebraic) surfaces, Computer Aided Geometric Design, v.26 n.6, p.627-647, August, 2009
	Abel J. P. Gomes , José F. M. Morgado , Edgar S. Pereira, A BSP-based algorithm for dimensionally nonhomogeneous planar implicit curves with topological guarantees, ACM Transactions on Graphics (TOG), v.28 n.2, p.1-24, April 2009
	Dimitrios I. Diochnos , Ioannis Z. Emiris , Elias P. Tsigaridas, On the asymptotic and practical complexity of solving bivariate systems over the reals, Journal of Symbolic Computation, v.44 n.7, p.818-835, July, 2009
	Kurt Mehlhorn , Michael Sagraloff, Isolating real roots of real polynomials, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea
	Jin-San Cheng , Xiao-Shan Gao , Jia Li, Root isolation for bivariate polynomial systems with local generic position method, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea
	Jinsan Cheng , Sylvain Lazard , Luis Peñaranda , Marc Pouget , Fabrice Rouillier , Elias Tsigaridas, On the topology of planar algebraic curves, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark