## Computational Geometry in C (2nd Ed.)

(Page numbers in braces only approximate.)
```   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.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}
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}
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}
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}