Article

Fast and exact geometric analysis of real algebraic plane curves

Authors:

Arno Eigenwillig,

Michael Kerber,

Nicola WolpertAuthors Info & Claims

ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

Pages 151 - 158

https://doi.org/10.1145/1277548.1277570

Published: 29 July 2007 Publication History

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

[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]

D. Arnon, G. Collins, S. McCallum: "Cylindrical Algebraic Decomposition I: the Basic Algorithm". SIAM J. Comp. 13 (1984) 865--877.

Digital Library

[3]

D. Arnon, G. Collins, S. McCallum: "Cylindrical Algebraic Decomposition II: an Adjacency Algorithm for the Plane". SIAM J. Comp. 13 (1984) 878--889.

Digital Library

[4]

S. Basu, R. Pollack, M.-F. Roy: Algorithms in Real Algebraic Geometry. Springer, 2nd edn., 2006.

Digital Library

[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.

Digital Library

[6]

C. W. Brown: "Constructing Cylindrical Algebraic Decompositions of the Plane Quickly", 2002. URL http://www.cs.usna.edu/~wcbrown/. Unpublished.

[7]

G. Collins: "Quantifier Elimination For Real Closed Fields By Cylindrical Algebraic Decomposition". In: Proc. 2nd GI Conf. on Automata Theory and Formal Languages, LNCS, vol. 33. Springer, 1975 134--183. Reprinted with corrections in: B. F. Caviness, J. R. Johnson (eds.), Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 85--121, Springer, 1998.

Digital Library

[8]

G. Collins, A. Akritas: "Polynomial Real Root Isolation Using Descartes' Rule of Signs". In: R. Jenks (ed.) Proc. of the third ACM symp. on Symb. and Alg. Comp. ACM, 1976 272--275.

Digital Library

[9]

G. Collins, J. Johnson, W. Krandick: "Interval Arithmetic in Cylindrical Algebraic Decomposition". J. Symb. Comp. 34 (2002) 143--155.

Digital Library

[10]

L. Ducos: "Optimizations of the Subresultant Algorithm". J. Pure Appl. Alg. 145 (2000) 149--163.

[11]

A. Eigenwillig: "On Multiple Roots in Descartes' Rule and Their Distance to Roots of Higher Derivatives"'. J. Comp. Appl. Math. 200 (2007) 226--230.

Digital Library

[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.

Digital Library

[13]

A. Eigenwillig, V. Sharma, C. Yap: "Almost Tight Recursion Tree Bounds for the Descartes Method". In: Proc. of the 2006 Int. Symp. on Symb. and Alg. Comp. (ISSAC 2006). ACM, 2006 71--78.

Digital Library

[14]

L. Gonzalez-Vega, M. El Kahoui: "An Improved Upper Complexity Bound for the Topology Computation of a Real Algebraic Plane Curve". J. Compl. 12 (1996) 527--544.

Digital Library

[15]

L. Gonzalez-Vega, I. Necula: "Efficient Topology Determination of Implicitly Defined Algebraic Plane Curves". Comp. Aided Geom. Design 19 (2002) 719--743.

Digital Library

[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]

H. Hong: "An Efficient Method for Analyzing the Topology of Plane Real Algebraic Curves". Math. and Comp. Sim. 42 (1996) 571--582.

Digital Library

[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]

J. R. Johnson, W. Krandick, K. Lynch, D. G. Richardson, A. D. Ruslanov: "High-Performance Implementations of the Descartes Method". In: Proc. of the 2006 Int. Symp. on Symb. and Alg. Comp. (ISSAC 2006). ACM, 2006 154--161.

Digital Library

[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.

Digital Library

[22]

S. McCallum: "Factors of Iterated Resultants and Discriminants". J. Symb. Comp. 27 (1999) 367--385.

Digital Library

[23]

F. Rouillier, P. Zimmermann: "Efficient isolation of {a} polynomial's real roots". J. Comp. and Appl. Math. 162 (2004) 33--50.

Digital Library

[24]

R. Seidel, N. Wolpert: "On the Exact Computation of the Topology of Real Algebraic Curves". In: Proc. of the 21st Ann. ACM Symp. on Comp. Geom. (SCG 2005). ACM, 2005 107--115.

Digital Library

[25]

A. Strzebonski: "Cylindrical Algebraic Decomposition using validated numerics". J. Symb. Comp. 41 (2006) 1021--1038.

Cited By

Islam MPoteaux APrébet R(2023)Algorithm for Connectivity Queries on Real Algebraic CurvesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597081(345-353)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597081
Diatta DDiatta SRouillier FRoy MSagraloff M(2022)Bounds for Polynomials on Algebraic Numbers and Application to Curve TopologyDiscrete & Computational Geometry10.1007/s00454-021-00353-w67:3(631-697)Online publication date: 15-Feb-2022
https://doi.org/10.1007/s00454-021-00353-w
Diatta DRuatta O(2022)On the Topology of the Intersection Curve of Two Real Parameterized Algebraic SurfacesNonlinear Analysis, Geometry and Applications10.1007/978-3-031-04616-2_21(499-515)Online publication date: 6-Apr-2022
https://doi.org/10.1007/978-3-031-04616-2_21
Show More Cited By

Index Terms

Fast and exact geometric analysis of real algebraic plane curves

Recommendations

Exact geometric-topological analysis of algebraic surfaces
SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometry

We present a method to compute the exact topology of a real algebraic surface S, implicitly given by a polynomial f ∈ Q[x;y;z] of arbitrary degree N. Additionally, our analysis provides geometric information as it supports the computation of arbitrary ...
On the exact computation of the topology of real algebraic curves
SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry

We consider the problem of computing a representation of the plane graph induced by one (or more) algebraic curves in the real plane. We make no assumptions about the curves, in particular we allow arbitrary singularities and arbitrary intersection. ...
On the computation of the topology of a non-reduced implicit space curve
ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation

An algorithm is presented for the computation of the topology of a non-reduced space curve defined as the intersection of two implicit algebraic surfaces.

It computes a Piecewise Linear Structure (PLS) isotopic to the original space curve.

The algorithm ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

July 2007

406 pages

ISBN:9781595937438

DOI:10.1145/1277548

General Chair:
Dongming Wang
Beihang University and UPMC-CNRS (China/France)

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 July 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISSAC07

Sponsor:

ISSAC07: International Symposium on Symbolic and Algebraic Computation

July 29 - August 1, 2007

Ontario, Waterloo, Canada

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
202
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Islam MPoteaux APrébet R(2023)Algorithm for Connectivity Queries on Real Algebraic CurvesProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597081(345-353)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597081
Diatta DDiatta SRouillier FRoy MSagraloff M(2022)Bounds for Polynomials on Algebraic Numbers and Application to Curve TopologyDiscrete & Computational Geometry10.1007/s00454-021-00353-w67:3(631-697)Online publication date: 15-Feb-2022
https://doi.org/10.1007/s00454-021-00353-w
Diatta DRuatta O(2022)On the Topology of the Intersection Curve of Two Real Parameterized Algebraic SurfacesNonlinear Analysis, Geometry and Applications10.1007/978-3-031-04616-2_21(499-515)Online publication date: 6-Apr-2022
https://doi.org/10.1007/978-3-031-04616-2_21
Jin KCheng J(2021)On the Complexity of Computing the Topology of Real Algebraic Space CurvesJournal of Systems Science and Complexity10.1007/s11424-020-9164-2Online publication date: 12-Jan-2021
https://doi.org/10.1007/s11424-020-9164-2
Jin KCheng J(2020)Isotopic Meshing of a Real Algebraic Space CurveJournal of Systems Science and Complexity10.1007/s11424-020-8378-733:4(1275-1296)Online publication date: 8-Aug-2020
https://doi.org/10.1007/s11424-020-8378-7
Shen LPérez-Díaz SGoldman RFeng Y(2019)Representing rational curve segments and surface patches using semi-algebraic setsComputer Aided Geometric Design10.1016/j.cagd.2019.10177074:COnline publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1016/j.cagd.2019.101770
Kerber MSagraloff M(2015)Root refinement for real polynomials using quadratic interval refinementJournal of Computational and Applied Mathematics10.1016/j.cam.2014.11.031280:C(377-395)Online publication date: 15-May-2015
https://dl.acm.org/doi/10.1016/j.cam.2014.11.031
Jin KCheng JGao X(2015)On the Topology and Visualization of Plane Algebraic CurvesProceedings of the 17th International Workshop on Computer Algebra in Scientific Computing - Volume 930110.1007/978-3-319-24021-3_19(245-259)Online publication date: 14-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-24021-3_19
Jin KCheng JZhi LWatt S(2014)Isotopic epsilon-meshing of real algebraic space curvesProceedings of the 2014 Symposium on Symbolic-Numeric Computation10.1145/2631948.2631970(118-127)Online publication date: 28-Jul-2014
https://dl.acm.org/doi/10.1145/2631948.2631970
Diatta DRouillier FRoy MNagasaka KWinkler FSzanto A(2014)On the computation of the topology of plane curvesProceedings of the 39th International Symposium on Symbolic and Algebraic Computation10.1145/2608628.2608670(130-137)Online publication date: 23-Jul-2014
https://dl.acm.org/doi/10.1145/2608628.2608670
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents