**Mathematical Surveys and Monographs**

Volume: 152;
2009;
235 pp;
Hardcover

MSC: Primary 05; 52; 68;

Print ISBN: 978-0-8218-4691-9

Product Code: SURV/152

List Price: $81.00

AMS Member Price: $64.80

MAA Member Price: $72.90

**Electronic ISBN: 978-1-4704-1379-8
Product Code: SURV/152.E**

List Price: $81.00

AMS Member Price: $64.80

MAA Member Price: $72.90

#### You may also like

#### Supplemental Materials

# Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures

Share this page
*János Pach; Micha Sharir*

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 collaborators, this volume provides a
comprehensive up-to-date survey of several core areas of combinatorial
geometry. It describes the beginnings of the subject, going back to the
nineteenth century (if not to Euclid), and explains why counting
incidences and estimating the combinatorial complexity of various
arrangements of geometric objects became the theoretical backbone of
computational geometry in the 1980s and 1990s. The combinatorial
techniques outlined in this book have found applications in many areas of
computer science from graph drawing through hidden surface removal and
motion planning to frequency allocation in cellular networks.

Combinatorial Geometry and Its Algorithmic Applications is
intended as a source book for professional mathematicians and computer
scientists as well as for graduate students interested in combinatorics
and geometry. Most chapters start with an attractive, simply formulated,
but often difficult and only partially answered mathematical question, and
describes the most efficient techniques developed for its solution. The
text includes many challenging open problems, figures, and an extensive
bibliography.

#### Readership

Graduate students and research mathematicians interested in combinatorial geometry and algorithmic applications.

#### Table of Contents

# Table of Contents

## Combinatorial Geometry and Its Algorithmic Applications: The Alcala Lectures

- Contents v7 free
- Preface and Apology vii9 free
- Chapter 1. Sylvester-Gallai Problem: .... 111 free
- Chapter 2. Arrangement of Surfaces: .... 1323
- Chapter 3. Davenport-Schinzel Sequences: ..... 7383
- Chapter 4. Incidences and Their Relatives: .... 99109
- Chapter 5. Crossing Numbers of Graphs: .... 119129
- Chapter 6. Extremal Combinatorics: 133143
- Chapter 7. Lines in Space: From Ray Shooting.... 147157
- Chapter 8. Geometric Coloring Problems: Sphere Packings.... 173183
- Chapter 9. From Sam Loyd to Laszlo Fejes Toth: The 15 Puzzle.... 183193
- Bibliography 197207
- Index 227237 free