Davenport–Schinzel Sequences and their Geometric Applications

A comprehensive treatment of a fundamental tool for solving problems in computational and combinatorial geometry.

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.These sequences exhibit some surprising properties that make them a fascinating subject for research in combinatorial analysis. This 1995 book on the subject by two of its leading researchers will be an important resource for students and professionals in combinatorics, computational geometry and related fields.