Preface and Apology These lecture notes are a compilation of surveys of the topics that were pre- sented in a series of talks at Alcal´ a, Spain, August 31 – September 5, 2006, by J´ Pach and Micha Sharir. To a large extent, these surveys are adapted from earlier papers written by the speakers and their collaborators. In their present form, the notes aptly describe both the history and the state of the art of these topics. The notes are arranged in an order that roughly parallels the order of the talks. Chapter 1 describes the beginnings of combinatorial geometry: Starting with Sylvester’s problem on the existence of “ordinary lines,” we introduce a number of exciting problems on incidences between points and lines in the plane and in space. This chapter uses the material in Pach, Pinchasi, and Sharir [588, 589]. In Chapter 2 we survey many aspects of the theory of arrangements of surfaces in higher dimensions. It is adapted from Agarwal and Sharir [51]. Readers that have some familiarity with the basic theory of arrangements can start their reading on this topic from this chapter, while those that are complete novices may find it useful to look first at Chapter 3, which studies arrangements of curves in the plane, with special emphasis on Davenport–Schinzel sequences and the major role they play in the theory of arrangements. This chapter is adapted from Agarwal and Sharir [52]. Chapter 4 covers the topic of incidences between points and curves and its many relatives, where a surge of activity has taken place in the past decade. It is adapted from two similar surveys by Pach and Sharir [600, 601]. The study of combinatorial and topological properties of planar arrangements of curves has become a separate discipline in discrete and computational geometry, under the name of Graph Drawing. Some basic aspects of this emerging discipline are dis- cussed in Chapter 5, which is based on the survey by Pach [583]. Some classical questions of Erd˝ os on repeated interpoint distances in a finite point set can be re- formulated as problems on the maximum number of incidences between points and circles, spheres, etc. In fact, these questions motivated and strongly influenced the early development of the theory of incidences a quarter of a century ago and they led to the discovery of powerful new combinatorial and topological tools. Many of Erd˝ os’s questions can be naturally generalized to problems on larger repeated subpatterns in finite point sets. Based on Brass and Pach [175], in Chapter 6 we outline some of the most challenging open problems of this kind, whose solution would have interesting consequences in pattern matching and recognition. Chapter 7 treats the special topic of lines in three-dimensional space, which is a nice application (or showpiece, if you will) of the general theory of arrange- ments on one hand, and shows up in a variety of only loosely related topics, ranging from ray shooting and hidden surface removal in computer graphics to geometric transversal theory. This chapter partially builds upon a somewhat old paper by Chazelle, Edelsbrunner, Guibas, Sharir, and Stolfi [220], but its second half is new, vii

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2009 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.