A polynomial-time algorithm for the topological type of real algebraic curve
type: Item
instance of: scholarly article
title: A polynomial-time algorithm for the topological type of real algebraic curve
zbMATH Open document ID: 0664.14017
DOI: 10.1016/S0747-7171(88)80013-0
author: Dennis S. Arnon
author: Scott McCallum
published in: Journal of Symbolic Computation
publication date: 1988-01-01T00:00:00Z
review text: An algorithm is presented for computing the topological type of a nonsingular real-algebraic curve on a projective plane. The topological type is a structure including (1) the parity of the degree of the curve; (2) the number of ovals into which the curve splits; (3) partial ordering of ovals by inclusion. The algorithm works for curves defined by integral homogeneous polynomials. It is based on cylindrical algebraic decomposition and has polynomial complexity assessed as a nice \(O(n^{27}L(d)^ 3)\) where n is the degree of the defining polynomial and L(d) is the total length of the coefficients.
Mathematics Subject Classification ID: 14H45
Mathematics Subject Classification ID: 14Pxx
Mathematics Subject Classification ID: 14-04
Mathematics Subject Classification ID: 14N05
zbMATH DE Number: 4085805
zbMATH Keywords: computing the topological type of a nonsingular real-algebraic curve on a projective plane
zbMATH Keywords: ovals
MaRDI profile type: Publication
cites work: Q4091421
cites work: Cylindrical Algebraic Decomposition I: The Basic Algorithm
cites work: A cluster-based cylindrical algebraic decomposition algorithm
cites work: The complexity of elementary algebra and geometry
cites work: Q3952057
cites work: Q3222299
cites work: THE TOPOLOGY OF REAL PROJECTIVE ALGEBRAIC VARIETIES
cites work: Q3698903
cites work: How to give an Exposition of the Cech-Alexander-Spanier type Homology Theory
cites work: Q5510566
cites work: Q4119824
cites work: Q5807665
cites work: Hilbert's sixteenth problem
full work available at URL: s0747-7171(88)80013-0
OpenAlex ID: W1991344970
Recommended article: A polynomial-time algorithm for the topological type of real algebraic curve - extended abstract
Recommended article: On the complexity of computing the topology of real algebraic space curves
Recommended article: An improved upper complexity bound for the topology computation of a real algebraic plane curve
Recommended article: On the exact computation of the topology of real algebraic curves
Recommended article: Computation of the topology of real algebraic space curves
Recommended article: Algorithmical determination of the topology of a real algebraic surface
Recommended article: A worst-case bound for topology computation of algebraic curves
Recommended article: Polynomial complexity algorithms for computational problems in the theory of algebraic curves
Recommended article: Q4712895
Recommended article: Computing the topology of an arrangement of implicitly defined real algebraic plane curves
description: scientific article; zbMATH DE number 4085805