View source for Davenport–Schinzel Sequences and Their Geometric Applications

{{italic title}}
'''''Davenport–Schinzel Sequences and Their Geometric Applications''''' is a book in [[Discrete geometry|discrete geometry]]. It was written by [[Biography:Micha Sharir|Micha Sharir]] and [[Biography:Pankaj K. Agarwal|Pankaj K. Agarwal]], and published by {{wipe|Cambridge University Press}} in 1995, with a paperback reprint in 2010.

==Topics==
[[Davenport–Schinzel sequence]]s are named after [[Biography:Harold Davenport|Harold Davenport]] and [[Biography:Andrzej Schinzel|Andrzej Schinzel]], who applied them to certain problems in the theory of [[Differential equation|differential equation]]s.{{r|ph}} They are finite sequences of symbols from a given [[Alphabet (formal languages)|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>k</math>, the longest allowed alternations have length <math>k</math>. For instance, a Davenport–Schinzel sequence of order three could have two symbols <math>x</math> and <math>y</math> that appear either in the order <math>x\dots y\dots x</math> or <math>y\dots x\dots y</math>, but longer alternations like <math>x\dots y\dots x\dots y</math> would be forbidden. The length of such a sequence, for a given choice of <math>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|discrete geometry]], for instance showing that the unbounded face of an [[Arrangement of lines|arrangement]] of [[Line segment|line segment]]s 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.{{r|hb}}

The first three chapters of the book provide bounds on the lengths of Davenport–Schinzel sequences whose superlinearity is described in terms of the [[Ackermann function#Inverse|inverse Ackermann function]] <math>\alpha(n)</math>. For instance, the length of a Davenport–Schinzel sequence of order three, with <math>n</math> symbols, can be at most <math>\Theta(n\alpha(n))</math>,{{r|ir}} 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.{{r|ph}}

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,{{r|ph}} following which the final chapter (comprising a large fraction of the book) concerns applications of these combinatorial bounds to problems including [[Voronoi diagram]]s and [[Nearest neighbor search|nearest neighbor search]], the construction of transversal lines through systems of objects, [[Visibility polygon|visibility problems]], and [[Motion planning|robot motion planning]].{{r|zn}} The topic remains an active area of research and the book poses many open questions.{{r|ph}}

==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".{{r|ph}}

==References==
{{reflist|refs=

<ref name=hb>{{citation
 | last = Brönnimann | first = Hervé
 | journal = zbMATH
 | title = Review of ''Davenport–Schinzel Sequences and Their Geometric Applications''
 | zbl=0834.68113}}</ref>

<ref name=ir>{{citation
 | journal = [[Mathematical Reviews]]
 | mr = 1329734
 | title = Review of ''Davenport–Schinzel Sequences and Their Geometric Applications''
 | year = 1996}}</ref>

<ref name=ph>{{citation
 | last = Hajnal | first = Peter
 | date = December 1996
 | doi = 10.1137/1038138
 | issue = 4
 | journal = SIAM Review
 | jstor = 2132953
 | pages = 689–691
 | title = Review of ''Davenport–Schinzel Sequences and Their Geometric Applications''
 | volume = 38}}</ref>

<ref name=zn>{{citation
 | last = Nagy | first = Zoltán
 | date = July 1998
 | doi = 10.1017/s0263574798241087
 | issue = 4
 | journal = Robotica
 | pages = 475–476
 | title = Review of ''Davenport–Schinzel Sequences and Their Geometric Applications''
 | volume = 16}}</ref>

}}

{{DEFAULTSORT:Davenport-Schinzel Sequences and Their Geometric Applications}}
[[Category:Discrete geometry]]
[[Category:Mathematics books]]

{{Sourceattribution|Davenport–Schinzel Sequences and Their Geometric Applications}}