This interesting paper deals with a fruitful and central area of research, where classical constructive algebra in the form of computer algebra, complexity theory and algebraic geometry come together. Besides throwing new light on each of the fields mentioned, there is an abundant variety of applications within science and engineering. Thus for instance, in the theory of robotics one of the most important problems is that of determining collision-free paths in the presence of obstructions. This is one of the main areas of applications for the theory dealt with by the paper under review. Let \(P\subset {\mathbb{Z}}[x_ 1,...,x_ r]\) be a finite set. The paper describes and analyzes a variant of the algorithm of Collins and others for decomposing \({\mathbb{R}}^ r\) into semi-algebraic cells so that the value of each \(f\in P\) has constant sign (positive, negative or zero) on the points of each cell. With this approach, the boundary of each cell is the disjoint union of lower-dimensional cells. For each bounded cell \(\alpha\) the pair (\({\bar \alpha}\),\(\alpha)\) is homeomorphic to a closed ball and its interior. Moreover, an algorithm is presented which for fixed r computes incidence of cells in polynomial time. Finally a priori estimates of the accuracy of approximations of roots of polynomials required in order to determine the combinatorial structure of the cell complex are given. This avoids computation in algebraic number fields.