Davenport–Schinzel Sequences and their Geometric Applications

Provides a comprehensive treatment of Davenport-Schinzel sequences, one of the most fundamental and sophisticated tools for solving problems in computational and combinatorial geometry. Applications arise in areas as diverse as robot motion planning, computer graphics and pattern matching.