English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  On the Exact Computation of the Topology of Real Algebraic Curves

Seidel, R., & Wolpert, N. (2005). On the Exact Computation of the Topology of Real Algebraic Curves. In Proceedings of the 21st ACM Symposium on Computational Geometry (pp. 107-115). New York, USA: ACM.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2734-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-2735-D
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Seidel, Raimund, Author
Wolpert, Nicola1, Author           
Mitchell, Joseph S. B., Editor
Rote, Günter, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2006-06-132005
 Publication Status: Issued
 Pages: -
 Publishing info: New York, USA : ACM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 279133
Other: Local-ID: C1256428004B93B8-20CFD87F1A1A99F0C1256F8C004E58ED-sw-ectrac-05
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Pisa, Italy
Start-/End Date: 2005-06-06

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the 21st ACM Symposium on Computational Geometry
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: New York, USA : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 107 - 115 Identifier: ISBN: 1-58113-991-8