Davenport–Schinzel Sequences and Their Geometric Applications
Davenport–Schinzel Sequences and Their Geometric Applications is a book in discrete geometry. It was written by Micha Sharir and Pankaj K. Agarwal, and published by Cambridge University Press in 1995, with a paperback reprint in 2010. Topics. Davenport–Schinzel sequences are named after Harold Davenport and Andrzej Schinzel, who applied them to certain problems in the theory of differential equations. They are finite sequences of symbols from a given alphabet, constrained by forbidding pairs of symbols from appearing in alternation more than a given number of times (regardless of what other symbols  might separate them). In a Davenport–Schinzel sequence of order formula_1, the longest allowed alternations have length formula_1. For instance, a Davenport–Schinzel sequence of order three could have two symbols formula_3 and formula_4 that appear either in the order formula_5 or formula_6, but longer alternations like formula_7 would be forbidden. The length of such a sequence, for a given choice of formula_1, can be only slightly longer than its number of distinct symbols. This phenomenon has been used to prove corresponding near-linear bounds on various problems in discrete geometry, for instance showing that the unbounded face of an  arrangement of line segments can have complexity that is only slightly superlinear. The book is about this family of results, both on bounding the lengths of Davenport–Schinzel sequences and on their applications to discrete geometry. The first three chapters of the book provide bounds on the lengths of Davenport–Schinzel sequences whose superlinearity is described in terms of the inverse Ackermann function formula_9. For instance, the length of a Davenport–Schinzel sequence of order three, with formula_10 symbols, can be at most formula_11, as the second chapter shows; the third concerns higher orders. The fourth chapter applies this theory  to line segments, and includes a proof that the bounds proven using these tools are tight: there exist systems of line segments whose arrangement complexity matches the bounds on Davenport–Schinzel sequence length. The remaining chapters concern more advanced applications of these methods. Three chapters concern arrangements of curves in the plane, algorithms for arrangements, and higher-dimensional arrangements, following which the final chapter (comprising a large fraction of the book) concerns applications of these combinatorial bounds to problems including Voronoi diagrams and nearest neighbor search, the construction of transversal lines through systems of objects, visibility problems, and robot motion  planning. The topic remains an active area of research and the book poses many open questions. Audience and reception. Although primarily aimed at researchers, this book (and especially its earlier chapters) could also be used as the textbook for a graduate course in its material. Reviewer Peter Hajnal calls it "very important to any specialist in computational geometry" and "highly recommended to anybody who is interested in this new topic at the border of combinatorics, geometry, and algorithm theory".