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 [math]\displaystyle{ k }[/math], the longest allowed alternations have length [math]\displaystyle{ k }[/math]. For instance, a Davenport–Schinzel sequence of order three could have two symbols [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] that appear either in the order [math]\displaystyle{ x\dots y\dots x }[/math] or [math]\displaystyle{ y\dots x\dots y }[/math], but longer alternations like [math]\displaystyle{ x\dots y\dots x\dots y }[/math] would be forbidden. The length of such a sequence, for a given choice of [math]\displaystyle{ k }[/math], 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 [math]\displaystyle{ \alpha(n) }[/math]. For instance, the length of a Davenport–Schinzel sequence of order three, with [math]\displaystyle{ n }[/math] symbols, can be at most [math]\displaystyle{ \Theta(n\alpha(n)) }[/math], 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".