Intersection and Decomposition Algorithms for Planar Arrangements

Exploring algorithms for geometric arrangements and their applications

Pankaj K Agarwal author

Format:Paperback

Publisher:Cambridge University Press

Published:11th Aug '11

Currently unavailable, and unfortunately no date known when it will be back

Intersection and Decomposition Algorithms for Planar Arrangements cover

This book presents an in-depth exploration of geometric problems related to curve arrangements, offering valuable insights for researchers in the field. Intersection and Decomposition Algorithms for Planar Arrangements is essential for those studying computational geometry.

The study of geometric problems through the arrangements of curves in a plane is a significant area within computational geometry. Intersection and Decomposition Algorithms for Planar Arrangements, first published in 1991, delves into various challenges associated with the arrangement of lines, segments, and curves. This book provides a comprehensive examination of these geometric configurations, highlighting their importance in algorithmic applications.

One of the key topics addressed in the book is the proof of almost tight bounds on the length of (n,s)-Davenport–Schinzel sequences. This technique is crucial for achieving optimal bounds in numerous algorithmic problems. Additionally, the book explores the intersection problem, which is fundamental to understanding how different geometric entities interact within a plane. By dissecting these issues, the author sheds light on the complexities involved in geometric computation.

Furthermore, the book discusses methods to enhance the efficiency of partitioning algorithms, particularly those that help in constructing spanning trees with low stabbing numbers. These techniques prove to be versatile tools for solving a variety of geometric problems. With numerous applications examined, Intersection and Decomposition Algorithms for Planar Arrangements is a valuable resource for researchers in computational and combinatorial geometry, offering insights and solutions to intricate geometric challenges.

ISBN: 9780521168472

Dimensions: 229mm x 152mm x 17mm

Weight: 440g

296 pages