Arrangements

INTRODUCTION Given a finite collection S of geometric objects such as hyperplanes or spheres in R d , the arrangement A(S) is the decomposition of R d into connected open cells of dimensions 0; 1; : : :; d induced by S. Besides being interesting in their own right, arrangements of hyperplanes have served as a unifying structure for many problems in discrete and computational geometry. With the recent advances in the study of arrangements of curved (algebraic) surfaces, arrangements have emerged as the underlying structure of geometric problems in a variety of `physical world' application domains such as robot motion planning and computer vision. This chapter is devoted to arrangements of hyperplanes and of curved surfaces in low-dimensional Euclidean space, with an emphasis on combinatorics and algorithms. In the first section we i