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):

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

URL of the conference:


URL for downloading the paper:


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
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)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section