A baby step-giant step roadmap algorithm for general algebraic sets

Abstract: Let

m a t h r m R

be a real closed field and

m a t h r m D s u b s e t m a t h r m R

an ordered domain. We give an algorithm that takes as input a polynomial

Q i n m a t h r m D [X_{1}, l d o t s, X_{k}]

, and computes a description of a roadmap of the set of zeros,

m a t h r m Z e r (Q, m a t h r m R^{k})

, of

Q

in

m a t h r m R^{k}

. The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain

m a t h r m D

, is bounded by

d^{O (k s q r t k)}

, where

d = m a t h r m d e g (Q) g e 2

. As a consequence, there exist algorithms for computing the number of semi-algebraically connected components of a real algebraic set,

m a t h r m Z e r (Q, m a t h r m R^{k})

, whose complexity is also bounded by

d^{O (k s q r t k)}

, where

d = m a t h r m d e g (Q) g e 2

. The best previously known algorithm for constructing a roadmap of a real algebraic subset of

m a t h r m R^{k}

defined by a polynomial of degree

d

has complexity

d^{O (k^{2})}

.

Recommendations

Cites work

Cited in

(22)

This page was built for publication: A baby step-giant step roadmap algorithm for general algebraic sets