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:








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



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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 PM
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


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