212 Graduate Texts in Mathematics Editorial Board S. Axler F.W. Gehring K.A. Ribet Springer New York Berlin Heidelberg Barcelona Hong Kong London Milan Paris Singapore Tokyo Graduate Texts in Mathematics TAKEUTIIZARING. Introduction to 34 SPITZER. Principles of Random Walk. Axiomatic Set Theory. 2nd ed. 2nded. 2 OXTOBY. Measure and Category. 2nd ed. 35 ALEXANDERIWERMER. Several Complex 3 SCHAEFER. Topological Vector Spaces. Variables and Banach Algebras. 3rd ed. 2nded. 36 KELLEy/NAMIOKA et al. Linear 4 HILTON/STAMMBACH. A Course in Topological Spaces. Homological Algebra. 2nd ed. 37 MONK. Mathematical Logic. 5 MAC LANE. Categories for the Working 38 GRAUERT/FRIlZSCHE. Several Complex Mathematician. 2nd ed. Variables. 6 HUGHEs/PIPER. Projective Planes. 39 ARVESON. An Invitation to C*-Algebras. 7 SERRE. A Course in Arithmetic. 40 KEMENy/SNELL/KNAPP. Denumerable 8 TAKEUTIIZARING. Axiomatic Set Theory. Markov Chains. 2nd ed. 9 HUMPHREYS. Introduction to Lie Algebras 41 APOSTOL. Modular Functions and and Representation Theory. Dirichlet Series in Number Theory. 10 COHEN. A Course in Simple Homotopy 2nded. Theory. 42 SERRE. Linear Representations of Finite 11 CONWAY. Functions of One Complex Groups. Variable I. 2nd ed. 43 GlLLMAN/JERISON. Rings of Continuous 12 BEALS. Advanced Mathematical Analysis. Functions. 13 ANDERSON/fuLLER. Rings and Categories 44 KENDIG. Elementary Algebraic Geometry. of Modules. 2nd ed. 45 LoEVE. Probability Theory I. 4th ed. 14 GOLUBITSKy/GUILLEMIN. Stable Mappings 46 LoEVE. Probability Theory II. 4th ed. and Their Singularities. 47 MOISE. Geometric Topology in 15 BERBERIAN. Lectures in Functional Dimensions 2 and 3. Analysis and Operator Theory. 48 SACHSlWu. General Relativity for 16 WINTER. The Structure of Fields. Mathematicians. 17 ROSENBLATT. Random Processes. 2nd ed. 49 GRUENBERGIWEIR. Linear Geometry. 18 HALMos. Measure Theory. 2nded. 19 HALMOS. A Hilbert Space Problem Book. 50 EDWARDS. Fermat's Last Theorem. 2nded. 51 KLINGENBERG. A Course in Differential 20 HUSEMOLLER. Fibre Bundles. 3rd ed. Geometry. 21 HUMPHREYS. Linear Algebraic Groups. 52 HARTSHORNE. Algebraic Geometry. 22 BARNES/MACK. An Algebraic Introduction 53 MANIN. A Course in Mathematical Logic. to Mathematical Logic. 54 GRAVERlWATKINS. Combinatorics with 23 GREUB. Linear Algebra. 4th ed. Emphasis on the Theory of Graphs. 24 HOLMES. Geometric Functional Analysis 55 BROWN/PEARCY. Introduction to Operator and Its Applications. Theory I: Elements of Functional Analysis. 25 HEWITT/STROMBERG. Real and Abstract 56 MASSEY. Algebraic Topology: An Analysis. Introduction. 26 MANES. Algebraic Theories. 57 CRoWELL/Fox. Introduction to Knot 27 KELLEY. General Topology. Theory. 28 ZARISKIISAMUEL. Commutative Algebra. 58 KOBUTZ. p-adic Numbers, p-adic Vol.l. Analysis, and Zeta-Functions. 2nd ed. 29 ZARISKIISAMUEL. Commutative Algebra. 59 LANG. Cyclotomic Fields. Vol.lI. 60 ARNOW. Mathematical Methods in 30 JACOBSON. Lectures in Abstract Algebra I. Classical Mechanics. 2nd ed. Basic Concepts. 61 WHITEHEAD. Elements of Homotopy 31 JACOBSON. Lectures in Abstract Algebra II. Theory. Linear Algebra. 62 KARGAPOLOv/MERLZJAKOV. Fundamentals 32 JACOBSON. Lectures in Abstract Algebra of the Theory of Groups. Ill. Theory of Fields and Galois Theory. 63 BOLLOBAS. Graph Theory. 33 HIRSCH. Differential Topology. (continued after index) Jiff Matousek Lectures on Discrete Geometry With 206 Illustrations Springer Jin Matousek Department of Applied Mathematics Charles University Malostranske mim. 25 118 00 Praha 1 Czech Republic [email protected] Editorial Board S. Axler F. w. Gehring K.A. Ribet Mathematics Department Mathematics Department Mathematics Department San Francisco State East Hall University of California, University University of Michigan Berkeley San Francisco, CA 94132 Ann Arbor, MI 48109 Berkeley, CA 94720-3840 USA USA USA [email protected] [email protected]. [email protected] umich.edu Mathematics Subject Classification (2000): 52-01 Library of Congress Cataloging-in-Publication Data Matousek, mf. Lectures on discrete geometry / Jin Matousek. p. cm. - (Graduate texts in mathematics; 212) Includes bibliographical references and index. ISBN 978-0-387-95374-8 ISBN 978-1-4613-0039-7 (eBook) 00110.1007/978-1-4613-0039-7 I. Convex geometry. 2. Combinatorial geometry. I. Title. II. Series. QA639.5 .M37 2002 516--dc21 2001054915 Printed on acid-free paper. © 2002 Springer-Verlag New York, Inc. Al! rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer-Verlag New York, Inc., 175 Fifth Avenue, New York, NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer soft ware, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this pUblication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Production managed by Michael Koy; manufacturing supervised by Jacqui Ashri. Typesetting: Pages created by author using Springer TeX macro package. 9 8 7 6 5 4 3 2 1 Springer-Verlag New York Berlin Heidelberg A member of BerteismannSpringer Science+Business Media GmbH Preface The next several pages describe the goals and the main topics of this book. Questions in discrete geometry typically involve finite sets of points, lines, circles, planes, or other simple geometric objects. For example, one can ask, what is the largest number of regions into which n lines can partition the plane, or what is the minimum possible number of distinct distances occur ring among n points in the plane? (The former question is easy, the latter one is hard.) More complicated objects are investigated, too, such as convex polytopes or finite families of convex sets. The emphasis is on "combinato rial" properties: Which of the given objects intersect, or how many points are needed to intersect all of them, and so on. Many questions in discrete geometry are very natural and worth studying for their own sake. Some of them, such as the structure of 3-dimensional convex polytopes, go back to the antiquity, and many of them are motivated by other areas of mathematics. To a working mathematician or computer scientist, contemporary discrete geometry offers results and techniques of great diversity, a useful enhancement of the "bag of tricks" for attacking problems in her or his field. My experience in this respect comes mainly from combinatorics and the design of efficient algorithms, where, as time progresses, more and more of the first-rate results are proved by methods drawn from seemingly distant areas of mathematics and where geometric methods are among the most prominent. The development of computational geometry and of geometric methods in combinatorial optimization in the last 20-30 years has stimulated research in discrete geometry a great deal and contributed new problems and motivation. Parts of discrete geometry are indispensable as a foundation for any serious study of these fields. I personally became involved in discrete geometry while working on geometric algorithms, and the present book gradually grew out of lecture notes initially focused on computational geometry. (In the meantime, several books on computational geometry have appeared, and so I decided to concentrate on the nonalgorithmic part.) In order to explain the path chosen in this book for exploring its subject, let me compare discrete geometry to an Alpine mountain range. Mountains can be explored by bus tours, by walking, by serious climbing, by playing vi Preface in the local casino, and in many other ways. The book should provide safe trails to a few peaks and lookout points (key results from various subfields of discrete geometry). To some of them, convenient paths have been marked in the literature, but for others, where only climbers' routes exist in research papers, I tried to add some handrails, steps, and ropes at the critical places, in the form of intuitive explanations, pictures, and concrete and elementary proofs.l However, I do not know how to build cable cars in this landscape: Reaching the higher peaks, the results traditionally considered difficult, still needs substantial effort. I wish everyone a clear view of the beautiful ideas in the area, and I hope that the trails of this book will help some readers climb yet unconquered summits by their own research. (Here the shortcomings of the Alpine analogy become clear: The range of discrete geometry is infinite and no doubt, many discoveries lie ahead, while the Alps are a small spot on the all too finite Earth.) This book is primarily an introductory textbook. It does not require any special background besides the usual undergraduate mathematics (linear al gebra, calculus, and a little of combinatorics, graph theory, and probability). It should be accessible to early graduate students, although mastering the more advanced proofs probably needs some mathematical maturity. The first and main part of each section is intended for teaching in class. I have actually taught most of the material, mainly in an advanced course in Prague whose contents varied over the years, and a large part has also been presented by students, based on my writing, in lectures at special seminars (Spring Schools of Combinatorics). A short summary at the end of the book can be useful for reviewing the covered material. The book can also serve as a collection of surveys in several narrower subfields of discrete geometry, where, as far as I know, no adequate recent treatment is available. The sections are accompanied by remarks and biblio graphic notes. For well-established material, such as convex polytopes, these parts usually refer to the original sources, point to modern treatments and surveys, and present a sample of key results in the area. For the less well cov ered topics, I have aimed at surveying most of the important recent results. For some of them, proof outlines are provided, which should convey the main ideas and make it easy to fill in the details from the original source. Topics. The material in the book can be divided into several groups: • Foundations (Sections 1.1-1.3, 2.1, 5.1-5.4, 5.7, 6.1). Here truly basic things are covered, suitable for any introductory course: linear and affine subspaces, fundamentals of convex sets, Minkowski's theorem on lattice points in convex bodies, duality, and the first steps in convex polytopes, Voronoi diagrams, and hyperplane arrangements. The remaining sections of Chapters 1, 2, and 5 go a little further in these topics. 1 I also wanted to invent fitting names for the important theorems, in order to make them easier to remember. Only few of these names are in standard usage. Preface Vll • Combinatorial complexity of geometric configurations (Chapters 4, 6, 7, and 11). The problems studied here include line-point incidences, com plexity of arrangements and lower envelopes, Davenport-Schinzel se quences, and the k-set problem. Powerful methods, mainly probabilistic, developed in this area are explained step by step on concrete nontriv ial examples. Many of the questions were motivated by the analysis of algorithms in computational geometry. • Intersection patterns and transversals of convex sets. Chapters 8-10 con tain, among others, a proof of the celebrated (p, q)-theorem of Alon and Kleitman, including all the tools used in it. This theorem gives a suffi cient condition guaranteeing that all sets in a given family of convex sets can be intersected by a bounded (small) number of points. Such results can be seen as far-reaching generalizations of the well-known ReIly's the orem. Some of the finest pieces of the weaponry of contemporary discrete and computational geometry, such as the theory of the VC-dimension or the regularity lemma, appear in these chapters. • Geometric Ramsey theory (Chapters 3 and 9). Ramsey-type theorems guarantee the existence of a certain "regular" subconfiguration in every sufficiently large configuration; in our case we deal with geometric ob jects. One of the historically first results here is the theorem of Erdos and Szekeres on convex independent subsets in every sufficiently large point set. • Polyhedral combinatorics and high-dimensional convexity (Chapters 12- 14). Two famous results are proved as a sample of polyhedral combina torics, one in graph theory (the weak perfect graph conjecture) and one in theoretical computer science (on sorting with partial information). Then the behavior of convex bodies in high dimensions is explored; the high lights include a theorem on the volume of an N-vertex convex polytope in the unit ball (related to algorithmic hardness of volume approxima tion), measure concentration on the sphere, and Dvoretzky's theorem on almost-spherical sections of convex bodies. • Representing finite metric spaces by coordinates (Chapter 15). Given an n-point metric space, we would like to visualize it or at least make it com putationally more tractable by placing the points in a Euclidean space, in such a way that the Euclidean distances approximate the given dis tances in the finite metric space. We investigate the necessary error of such approximation. Such results are of great interest in several areas; for example, recently they have been used in approximation algorithms in combinatorial optimization (multicommodity flows, VLSI layout, and others). These topics surely do not cover all of discrete geometry, which is a rather vague term anyway. The selection is (necessarily) subjective, and naturally I preferred areas that I knew better and/or had been working in. (Unfortu nately, I have had no access to supernatural opinions on proofs as a more viii Preface reliable guide.) Many interesting topics are neglected completely, such as the wide area of packing and covering, where very accessible treatments exist, or the celebrated negative solution by Kahn and Kalai of the Borsuk conjec ture, which I consider sufficiently popularized by now. Many more chapters analogous to the fifteen of this book could be added, and each of the fifteen chapters could be expanded into a thick volume. But the extent of the book, as well as the time for its writing, are limited. Exercises. The sections are complemented by exercises. The little framed numbers indicate their difficulty: III is routine, 0 may need quite a bright idea. Some of the exercises used to be a part of homework assignments in my courses and the classification is based on some experience, but for others it is just an unreliable subjective guess. Some of the exercises, especially those conveying important results, are accompanied by hints given at the end of the book. Additional results that did not fit into the main text are often included as exercises, which saves much space. However, this greatly enlarges the danger of making false claims, so the reader who wants to use such information may want to check it carefully. Sources and further reading. A great inspiration for this book project and the source of much material was the book Combinatorial Geometry of Pach and Agarwal [PA95]. Too late did I become aware of the lecture notes by Ball [BaI97] on modern convex geometry; had I known these earlier I would probably have hesitated to write Chapters 13 and 14 on high-dimensional convexity, as I would not dare to compete with this masterpiece of mathe matical exposition. Ziegler's book [Zie94] can be recommended for studying convex polytopes. Many other sources are mentioned in the notes in each chapter. For looking up information in discrete geometry, a good starting point can be one of the several handbooks pertaining to the area: Handbook of Convex Geometry [GW93], Handbook of Discrete and Computational Ge ometry [G097], Handbook of Computational Geometry [SUOO], and (to some extent) Handbook of Combinatorics [GGL95], with numerous valuable sur veys. Many of the important new results in the field keep appearing in the journal Discrete and Computational Geometry. Acknowledgments. For invaluable advice and/or very helpful comments on preliminary versions of this book I would like to thank Micha Sharir, Gunter M. Ziegler, Yuri Rabinovich, Pankaj K. Agarwal, Pavel Valtr, Martin Klazar, Nati Linial, Gunter Rote, Janos Pach, Keith Ball, Uli Wagner, Imre Barany, Eli Goodman, Gyorgy Elekes, Johannes Blomer, Eva Matouskova, Gil Kalai, Joram Lindenstrauss, Emo Welzl, Komei Fukuda, Rephael Wenger, Piotr In dyk, Sariel Har-Peled, Vojtech Rodl, Geza T6th, Karoly Boroczky Jr., Rados Radoicic, Helena Nyklova, Vojtech Franek, Jakub Simek, Avner Magen, Gre gor Baudis, and Andreas Marwinski (I apologize if I forgot someone; my notes are not perfect, not to speak of my memory). Their remarks and suggestions Preface ix allowed me to improve the manuscript considerably and to eliminate many of the embarrassing mistakes. I thank David Kramer for a careful copy-editing and finding many more mistakes (as well as offering me a glimpse into the exotic realm of English punctuation). I also wish to thank everyone who par ticipated in creating the friendly and supportive environments in which I have been working on the book. Errors. If you find errors in the book, especially serious ones, I would appreciate it if you would let me know (email: [email protected]). I plan to post a list of errors at http://www.ms.mff.cuni.cz;-matousek. Prague, July 2001 Jin Matousek