This article is cited in
5 papers
Computing the dimension of a semi-algebraic set
S. Basua,
R. Pollackb,
M.-F. Royc a School of Mathematics, Georgia Institute of Technology
b Courant Institute of Mathematical Sciences
c University of Rennes 1
Abstract:
In this paper, we consider the problem of computing the real dimension of a given semi-algebraic subset of
$\mathbf{R}^k$, where
$\mathbf{R}$ is a real closed field. We prove that the
dimension,
$k'$, of a semi-algebraic set described by
$s$ polynomials of degree
$d$ in
$k$ variables can be computed in time
$$
\begin{cases}
s^{(k-k')k'}d^{O(k'(k-k'))},&\text{if}\ k'\geqslant k/2,\\
s^{(k-k'+1)(k'+1)}d^{O(k'(k-k'))},&\text{if}\ k'< k/2.
\end{cases}
$$
This result improves slightly the result proved in [22], where an algorithm with complexity bound
$(sd)^{O(k'(k-k'))}$ is described for the same problem. The complexity bound of the algorithm described in this paper has a better dependence on the number,
$s$, of polynomials
in the input.
UDC:
510.52+
512.7 Received: 17.10.2004
Language: English