Davenport-Schinzel Sequences and their Geometric Applications

by Micha Sharir, Pankaj K. Agarwal

Overview

Applications of Davenport-Schinzel sequences arise in areas as diverse as robot motion planning, computer graphics and vision, and pattern matching. These sequences exhibit some surprising properties that make them a fascinating subject for research in combinatorial analysis. This book provides a comprehensive study of the combinatorial properties of Davenport-Schinzel sequences and their numerous geometric applications. These sequences are sophisticated tools for solving problems in computational and combinatorial geometry. This first 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.

Product Details

ISBN-13:	9780521135115
Publisher:	Cambridge University Press
Publication date:	03/11/2010
Pages:	388
Product dimensions:	6.10(w) x 9.20(h) x 0.90(d)

Table of Contents

1. Introduction; 2. Davenport–Schinzel sequences of order 3; 3. Higher order sequences; 4. Geometric realization; 5. Planar arrangements; 6. Algorithms for arrangements; 7. Arrangements in higher dimensions; 8. Geometric applications; Bibliography.

Editorial Reviews

Review of the hardback: 'This is a very well written and readable book suitable as a textbook for upper undergraduate and junior graduate students. It is entirely selfcontained.' European Mathematical Society Newsletter

Review of the hardback: 'I am very impressed by the book and highly recommend it to anyone who is interested in computational geometry.' K. Kedem, The Computer Journal

From the Publisher