This book is primarily a textbook introduction to various areas of discrete geometry. In each
area, it explains several key results and methods, in an accessible and concrete manner. It …

Although there are many advanced and specialized texts and handbooks on algorithms,
until now there was no book that focused exclusively on the wide variety of data structures …

The arrangement of a finite collection of geometric objects is the decomposition of the space
into connected cells induced by them. We survey combinatorial and algorithmic properties of …

Given a finite collection S of geometric objects such as hyperplanes or spheres in Rd, the
arrangement A (S) is the decomposition of Rd into connected open cells of dimensions 0 …

In this paper, we give a new algorithm for quantifier elimination in the first order theory of real
closed fields that improves the complexity of the best known algorithm for this problem till …

Motion planning is a fundamental problem in robotics. It comes in a variety of forms, but the
simplest version is as follows. We are given a robot system B, which may consist of several …

" Based on a lecture series given by the authors at a satellite meeting of the 2006
International Congress of Mathematicians and on many articles written by them and their …

A classic result in real algebraic geometry due to Oleinik—Petrovskii, Thom and Milnor,
bounds the topological complexity (the sum of the Betti numbers) of basic semi-algebraic …

Let R be a set of pairwise-disjoint polyhedral obstacles in R3 with a total of n vertices, and let
B be a ball. We show that the combinatorial complexity of the free configuration space 3 of B …

In this paper we prove tight bounds on the combinatorial and topological complexity of sets
dened in terms of n denable sets belonging to some fixed denable family of sets in an o …