The non-scalar Model of Complexity in Computational Geometry
José Luis Montaña, Luis Miguel Pardo, Tomás Recio · Birkhäuser Boston eBooks · 1991
An outline on the relation between algebraic complexity theories and semialgebraic sets is presented. First we discuss the concepts of total and non-scalar complexities both for polynomials and semialgebraic sets observing that they are ”geometric complexities” verifying the ”semialgebraic” version of the Benedetti-Risler conjecture [4]. Moreover, we remark that total and non-scalar complexities of semialgebraic sets are decidable theories. Finally, using non-scalar complexity and intersection numbers of semialgebraic sets we get new lower bounds for several problems in computational geometry, generalizing the results obtained by M. Ben-Or using total complexity and number of connected components. An expanded version of the ideas sketched here is [10] These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.