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 …

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 …

Vertical decomposition is a widely used general technique for decomposing the cells of
arrangements of semi-algebraic sets in ℝd into constant-complexity subcells. In this paper …

In a typical range-emptiness searching (resp., reporting) problem, we are given a set P of n
points in R^d, and we wish to preprocess it into a data structure that supports efficient range …

Abstract Let T={\triangle _1, ...,\triangle _n\} T=▵ 1,…,▵ n be a set of n triangles in R^ 3 R 3
with pairwise-disjoint interiors, and let B be a convex polytope in R^ 3 R 3 with a constant …

We show that, for any fixed δ> 0, the combinatorial complexity of the union of n triangles in
the plane, each of whose angles is at least δ, is O (n 2α (n) log* n), with the constant of …

Let C be a family of n convex bodies in the plane, which can be decomposed into k
subfamilies of pairwise disjoint sets. It is shown that the number of tangencies between the …

We show that the combinatorial complexity of the union of n “fat” tetrahedra in 3-space (ie,
tetrahedra all of whose solid angles are at least some fixed constant) of arbitrary sizes, is O …

Abstract Let\(\mathscr {B}\) be a set of n unit balls in\({\mathbb {R}}^ 3\). We present a linear-
size data structure for storing\(\mathscr {B}\) that can determine in\(O^*(\sqrt {n})\) time …