MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Seidel, Raimund
Wolpert, Nicola
dblp
dblp
Not MPG Author(s):
Seidel, Raimund
Editor(s):
Mitchell, Joseph S. B.
Rote, Günter
dblp
dblp
BibTeX cite key*:
sw-ectrac-05
Title, Booktitle
Title*:
On the Exact Computation of the Topology of Real Algebraic Curves
Booktitle*:
Proceedings of the 21st ACM Symposium on Computational Geometry
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Pisa, Italy
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
6 June 2005
Event End Date:
8 June 2005
Publisher
Name*:
ACM
URL:
Address*:
New York, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
107-115
Year*:
2005
VG Wort Pages:
ISBN/ISSN:
1-58113-991-8
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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. This problem has been well studied for the case of a single curve. All proposed approaches to this problem so far require finding and counting real roots of polynomials over an algebraic extension of Q, i.e. the coefficients of those polynomials are algebraic numbers. Various algebraic approaches for this real root finding and counting problem have been developed, but they tend to be costly unless speedups via floating point approximations are introduced, which without additional checks in some cases can render the approach incorrect for some inputs.We propose a method that is always correct and that avoids finding and counting real roots of polynomials with non-rational coefficients. We achieve this using two simple geometric approaches: a triple projections method and a curve avoidance method. We have implemented our approach for the case of computing the topology of a single real algebraic curve. Even this prototypical implementation without optimizations appears to be competitive with other implementations.
URL for the Abstract:
http://doi.acm.org/10.1145/1064092.1064111
Download
Access Level:
Public

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



BibTeX Entry:

@INPROCEEDINGS{sw-ectrac-05,
AUTHOR = {Seidel, Raimund and Wolpert, Nicola},
EDITOR = {Mitchell, Joseph S. B. and Rote, G{\"u}nter},
TITLE = {On the Exact Computation of the Topology of Real Algebraic Curves},
BOOKTITLE = {Proceedings of the 21st ACM Symposium on Computational Geometry},
PUBLISHER = {ACM},
YEAR = {2005},
PAGES = {107--115},
ADDRESS = {Pisa, Italy},
ISBN = {1-58113-991-8},
}


Entry last modified by Christine Kiesel, 06/13/2006
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)
Nicola Wolpert
Created
01/17/2005 03:15:45 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
13.06.2006 12:54:03
13.06.2006 12:53:45
13.06.2006 12:53:37
22.04.2005 14:02:24
22.04.2005 14:01:30