Efficient simplicial replacement of semialgebraic sets

Abstract: We prove that for any

e l l g e q 0

, there exists an algorithm which takes as input a description of a semi-algebraic subset

S s u b s e t m a t h b b R^{k}

given by a quantifier-free first order formula

p h i

in the language of the reals, and produces as output a simplicial complex

D e l t a

, whose geometric realization,

| D e l t a |

is

e l l

-equivalent to

S

. The complexity of our algorithm is bounded by

(s d)^{k^{O (e l l)}}

, where

s

is the number of polynomials appearing in the formula

p h i

, and

d

a bound on their degrees. For fixed

e l l

, this bound is singly exponential in

k

. In particular, since

e l l

-equivalence implies that the homotopy groups up to dimension

e l l

of

| D e l t a |

are isomorphic to those of

S

, we obtain a reduction (having singly exponential complexity) of the problem of computing the first

e l l

homotopy groups of

S

to the combinatorial problem of computing the first

e l l

homotopy groups of a finite simplicial complex of size bounded by

(s d)^{k^{O (e l l)}}

.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Efficient simplicial replacement of semialgebraic sets