MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://www.cs.uwaterloo.ca/~issac07/
Downloading URL:
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
Note, Abstract, ©
(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},
 ADDRESS = {Waterloo, Ontario, Canada},
 MONTH = {July},
 ISBN = {978-1-59593-743-8},
 DOI = {10.1145/1277548.1277570},
}

Entry last modified by Michael Kerber, 02/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Michael Kerber		Created
08/09/2007 12:28:39
Revisions
2.
1.
0.

Editor(s)
Michael Kerber
Michael Kerber
Michael Kerber

Edit Dates
08/09/2007 12:40:13 PM
08/09/2007 12:37:45 PM
08/09/2007 12:28:40 PM

File Attachment Icon
ekw-fast-2007-authprep.pdf