Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Eigenwillig, Arno Kerber, Michael Wolpert, Nicola dblp dblp dblp Not MPG Author(s): Wolpert, Nicola
 Editor(s): Brown, Christopher W. dblp Not MPII Editor(s): Brown, Christopher W.
 BibTeX cite key*: ekw-fast-2007

 Title, Booktitle
 Title*: Fast and Exact Geometric Analysis of Real Algebraic Plane Curves ekw-fast-2007-authprep.pdf (296.06 KB) Booktitle*: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation

 Event, URLs
 URL of the conference: http://www.cs.uwaterloo.ca/~issac07/ URL for downloading the paper: Event Address*: Waterloo, Ontario, Canada Language: English Event Date* (no longer used): Organization: ACM Event Start Date: 29 July 2007 Event End Date: 1 August 2007

 Publisher
 Name*: ACM URL: http://www.acm.org/ Address*: New York, USA Type:

 Vol, No, Year, pp.
 Series:
 Volume: Number: Month: July Pages: 151-158 Year*: 2007 VG Wort Pages: ISBN/ISSN: 978-1-59593-743-8 Sequence Number: DOI: 10.1145/1277548.1277570

 (LaTeX) 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(\alpha,y)$ at a critical $x$-coordinate $\alpha$ are found with adaptive-precision arithmetic in all cases, using a variant of the Bitstream Descartes method~(Eigenwillig et~al., 2005). The algorithm may choose a generic coordinate system for parts of the analysis but provides its result in the original system. The algorithm has been implemented as C++ library \texttt{AlciX} in the EXACUS project. Running time comparisons with \texttt{top} by Gonzalez-Vega and Necula~(2002), and with \texttt{cad2d} by Brown demonstrate its efficiency. URL for the Abstract: http://portal.acm.org/citation.cfm?doid=1277548.1277570#abstract Keywords: Algebraic curves, cylindrical algebraic decomposition, topology computation, Descartes method, Sturm-Habicht sequence, exact geometric computation HyperLinks / References / URLs: http://portal.acm.org/citation.cfm?doid=1277548.1277570 Copyright Message: © ACM, 2007. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation (ISSAC 2007). http://doi.acm.org/10.1145/1277548.1277570 Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{ekw-fast-2007,
AUTHOR = {Eigenwillig, Arno and Kerber, Michael and Wolpert, Nicola},
EDITOR = {Brown, Christopher W.},
TITLE = {Fast and Exact Geometric Analysis of Real Algebraic Plane Curves},
BOOKTITLE = {Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation},
PUBLISHER = {ACM},
YEAR = {2007},
ORGANIZATION = {ACM},
PAGES = {151--158},