For the first decade or so of its existence, computational geometry was concerned primarily with a linear world: arrangements of points, lines, line segments and their higher dimensional analogues. In the past decade, motivated by questions in robotics, motion planning, computer vision, and learning theory, as well as by theoretical studies of arrangements in general, computational geometry has investigated arrangements of sets which cannot be described by linear equations and inequalities but are instead arrangements of ``semi-algebraic sets''. These are the solution sets of polynomial equalities and inequalities over the reals. The study of geometric, topological, algebraic and algorithmic issues about them constitutes a significant portion of real algebraic geometry.

We begin the talk with an introduction to the subject, presenting the ways in which it is both similar to and different from the linear world and introducing many of the problems in which we are primarily interested. This is followed by a discussion of earlier results and the techniques that have made increasingly efficient algorithms for these problems possible. We conclude by reporting on recent developments by the speaker together with S. Basu and M. F. Roy, which have produced improved algorithms for the existential theory of the reals, quantifier elimination over real closed fields, the computation of roadmaps for semi-algebraic sets and the computation of a semi-algebraic description of the connected components of a semi-algebraic set.