Table of Contents

   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}