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

El Kahoui, M'hammed

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

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

MPS-Authors

/persons/resource/persons44379

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

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

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.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-AB43-6

Abstract

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.