de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

An Improved Upper Complexity Bound for the Topology Computation of a Real Algebraic Plane Curve

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44379

El Kahoui,  M'hammed
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

El Kahoui, M. (1996). An Improved Upper Complexity Bound for the Topology Computation of a Real Algebraic Plane Curve. Journal of Complexity, 12(4), 527-544. Retrieved from http://www.sciencedirect.com/science?_ob=IssueURL&_tockey=%23TOC%236862%231996%23999879995%23308679%23FLT%23display%23Volume_12,_Issue_4,_Pages_255-624_(December_1996)%23tagged%23Volume%23first%3D12%23Issue%23first%3D4%23Pages%23first%3D255%23last%3D624%23date%23(December_1996)%23&_auth=y&view=c&_acct=C000004638&_version=1&_urlVersion=0&_userid=43521&md5=6759f47d24990790d346fac647d30de6.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-AB43-6
Zusammenfassung
The computation of the topological shape of a real algebraic plane curve is usually driven by the study of the behavior of the curve around its critical points (which includes also the singular points). In this paper we present a new algorithm computing the topological shape of a real algebraic plane curve whose complexity is better than the best algorithms known. This is due to the avoiding, through a sufficiently good change of coordinates, of real root computations on polynomials with coefficients in a simple real algebraic extension of $\mathbb{Q}$ to deal with the critical points of the considered curve. In fact, one of the main features of this algorithm is that its complexity is dominated by the characterization of the real roots of the discriminant of the polynomial defining the considered curve.