Preface {v} 1 Polygon Triangulation {1} 1.1 Art Gallery Theorems {1} 1.2 Triangulation: Theory {13} 1.3 Area of Polygon {19} 1.4 Implementation Issues {27} 1.5 Segment Intersection {32} 1.6 Triangulation: Implementation {37} 2 Polygon Partitioning {51} 2.1 Monotone Partitioning {51} 2.2 Trapezoidalization {54} 2.3 Partition into Monotone Mountains {59} 2.4 Linear-Time Triangulation {65} 2.5 Convex Partitioning {67} 3 Convex Hulls in Two Dimensions {73} 3.1 Definitions of Convexity and Convex Hulls {74} 3.2 Naive Algorithms for Extreme Points {77} 3.3 Gift Wrapping {79} 3.4 QuickHull {81} 3.5 Graham's Algorithm {84} 3.6 Lower Bound {101} 3.7 Incremental Algorithm {103} 3.8 Divide and Conquer {105} 3.9 Additional Exercises {111} 4 Convex Hulls in Three Dimensions {119} 4.1 Polyhedra {119} 4.2 Hull Algorithms {129} 4.3 Implementation of Incremental Algorithm {137} 4.4 Polyhedral Boundary Representations {170} 4.5 Randomized Incremental Algorithm {174} 4.6 Higher Dimensions {175} 4.7 Additional Exercises {178} 5 Voronoi Diagrams {181} 5.1 Applications: Preview {181} 5.2 Definitions and Basic Properties {183} 5.3 Delaunay Triangulations {188} 5.4 Algorithms {193} 5.5 Applications in Detail {198} 5.6 Medial Axis {210} 5.7 Connection to Convex Hulls {214} 5.8 Connection to Arrangements {224} 6 Arrangements {227} 6.1 Introduction {227} 6.2 Combinatorics of Arrangements {229} 6.3 Incremental Algorithm {234} 6.4 Three and Higher Dimensions {235} 6.5 Duality {236} 6.6 Higher-Order Voronoi Diagrams {241} 6.7 Applications {245} 6.8 Additional Exercises {255} 7 Search and Intersection 257 7.1 Introduction {257} 7.2 Segment-Segment Intersection {257} 7.3 Segment-Triangle Intersection {261} 7.4 Point in Polygon {279} 7.5 Point in Polyhedron {286} 7.6 Intersection of Convex Polygons {294} 7.7 Intersection of Segments {308} 7.8 Intersection of Nonconvex Polygons {311} 7.9 Extreme Point of Convex Polygon {314} 7.10 Extremal Polytope Queries {317} 7.11 Planar Point Location {332} 8 Motion Planning {343} 8.1 Introduction {343} 8.2 Shortest Paths {344} 8.3 Moving a Disk {350} 8.4 Translating a Convex Polygon {352} 8.5 Moving a Ladder {365} 8.6 Robot Arm Motion {376} 8.7 Separability {395} 9 Sources {405} 9.1 Bibliographies and FAQ's {405} 9.2 Textbooks {406} 9.3 Book Collections {407} 9.4 Monographs {408} 9.5 Journals {408} 9.6 Conference Proceedings {409} 9.7 Software {409} Bibliography {410}