## 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.1.1  Polygons     {1}
Definition of a Polygon     {1}
1.1.2  The Art Gallery Theorem     {3}
Problem Definition     {3}
Visibility     {3}
Max over Min Formulation     {4}
Empirical Exploration     {5}
Sufficiency of n.     {5}
Necessity for Small n.     {5}
Necessity of n/3     {7}
1.1.3  Fisk's Proof of Sufficiency     {7}
Diagonals and Triangulation     {8}
Three Coloring     {8}
1.1.4  Exercises     {11}
1.2  Triangulation: Theory     {13}
1.2.1  Existence of a Diagonal     {14}
1.2.2  Properties of Triangulations     {16}
1.2.3  Triangulation Dual     {16}
1.2.4  3-coloring Proof     {17}
1.2.5  Exercises     {18}
1.3  Area of Polygon     {19}
1.3.1  Area of a Triangle     {19}
1.3.2  Cross Product     {19}
1.3.3  Determinant Form     {20}
1.3.4  Area of a Convex Polygon     {20}
1.3.5  Area of a Convex Quadrilateral     {21}
1.3.6  Area of a Nonconvex Quadrilateral     {22}
1.3.7  Area from an Arbitrary Center     {23}
1.3.8  Volume in Three and Higher Dimensions     {25}
1.3.9  Exercises     {26}
1.4  Implementation Issues     {27}
1.4.1  Representation of a Point     {27}
Arrays versus Records     {27}
Integers versus Reals     {28}
Point Type Definition     {28}
1.4.2  Representation of a Polygon     {28}
1.4.3  Code for Area     {29}
1.5  Segment Intersection     {32}
1.5.1  Diagonals     {32}
1.5.2  Problems with Slopes     {32}
{1.5.3} |Left|     {33}
1.5.4  Boolean Inte        34
Improper Inte        {36
Betweenness     {36}
1.5.5  Segment Inte   Code     {37}
1.6  Triangulation: Implementation     {37}
1.6.1  Diagonals, internal or external     {37}
1.6.2  InCone     {38}
1.6.3  Diagonal     {40}
1.6.4  Exercises     {41}
1.6.5  Triangulation by Ear Removal     {41}
Diagonal-Based Algorithm     {42}
Ear Removal     {42}
Triangulation Code     {43}
1.6.6  Example     {44}
1.6.7  Analysis     {48}
1.6.8  Exercises     {49}
2  Polygon Partitioning     {51}
2.1  Monotone Partitioning     {51}
2.1.1  Monotone Polygons     {52}
Properties of Monotone Polygons     {52}
2.1.2  Triangulating a Monotone Polygon     {54}
2.2  Trapezoidalization     {54}
2.2.1  Plane sweep     {56}
2.2.2  Triangulation in O(n log n)     {58}
2.2.3  Exercises     {59}
2.3  Partition into Monotone Mountains     {59}
2.3.1  Monotone Mountains     {59}
2.3.2  Triangulating a Monotone Mountain     {60}
2.3.3  Adding Diagonals to Trapezoidalization     {61}
2.3.4  Exercises     {63}
2.4  Linear-Time Triangulation     {65}
2.4.1  Randomized Triangulation     {66}
2.5  Convex Partitioning     {67}
2.5.1  Optimum Partition     {67}
2.5.2  Hertel and Mehlhorn Algorithm     {69}
2.5.3  Optimal Convex Partitions     {70}
2.5.4  Exercises     {70}
3  Convex Hulls in Two Dimensions     {73}
3.1  Definitions of Convexity and Convex Hulls     {74}
3.1.1  Extreme points     {76}
3.2  Naive Algorithms for Extreme Points     {77}
3.2.1  Nonextreme points     {77}
3.2.2  Extreme Edges     {78}
3.2.3  Exercises     {78}
3.4  QuickHull     {81}
3.4.1  Exercises     {83}
3.5  Graham's Algorithm     {84}
3.5.1  Top Level Description     {84}
3.5.2  Pseudocode, Version A     {85}
3.5.3  Details: Boundary Conditions     {85}
Start and Stop of Loop     {86}
Sorting Origin     {86}
Collinearities     {87}
Hull Collinearities.     {87}
Sorting Collinearities.     {88}
Coincident Points.     {88}
3.5.4  Pseudocode, Version B     {89}
3.5.5  Implementation of Graham's Algorithm     {89}
Data Representation     {89}
Sorting     {90}
|FindLowest|.     {90}
Avoiding Floats.     {92}
|Atan2|.     {92}
Slopes.     {93}
|Left|.     {93}
|Qsort|.     {93}
|Compare|.     {94}
|Main|     {94}
Code for the Graham Scan     {96}
Example     {96}
3.5.6  Conclusion     {100}
3.5.7  Exercises     {100}
3.6  Lower Bound     {101}
3.7  Incremental Algorithm     {103}
3.7.1  Exercises     {105}
3.8  Divide and Conquer     {105}
3.8.1  Divide-and-Conquer Recurrence Relation     {106}
3.8.2  Algorithm Description     {106}
3.8.3  Analysis     {107}
3.8.4  Output-size Sensitive Optimal Algorithm     {110}
3.8.5  Exercises     {111}
3.9.1  Polygon Hull     {111}
3.9.2  Orthogonal polygons     {111}
3.9.3  Miscellaneous Hull-Related     {113}
4  Convex Hulls in Three Dimensions     {119}
4.1  Polyhedra     {119}
4.1.1  Introduction     {119}
4.1.2  Regular Polytopes     {123}
4.1.3  Euler's Formula     {125}
4.1.4  Proof of Euler's Formula     {125}
4.1.5  Consequence: Linearity     {127}
4.1.6  Exercises     {127}
4.2  Hull Algorithms     {129}
4.2.2  Divide and Conquer     {129}
Exercises     {134}
4.2.3  Incremental Algorithm     {134}
Complexity Analysis     {136}
4.3  Implementation of Incremental Algorithm     {137}
4.3.1  Data Structures     {137}
Structure definitions.     {137}
Example of Data Structures.     {139}
Basic List Processing.     {142}
|structs|: Full Detail.     {142}
4.3.2  Example: Cube     {145}
|main|.     {145}
|DoubleTriangle|.     {145}
|ConstructHull|.     {149}
|VolumeSign|.     {153}
Coplanarity Revisited.     {156}
|MakeConeFace|.     {156}
|CleanUp|.     {157}
4.3.3  Checks     {162}
4.3.4  Performance     {162}
4.3.5  Volume Overflow     {165}
Exercises     {168}
4.4  Polyhedral Boundary Representations     {170}
4.4.1  Winged-edge Data Structure     {170}
4.4.2  Twin-edge Data Structure     {171}
4.4.4  Exercises     {174}
4.5  Randomized Incremental Algorithm     {174}
4.5.1  Exercises     {175}
4.6  Higher Dimensions     {175}
4.6.1  Coordinates     {175}
4.6.2  Hypercube     {176}
4.6.3  Regular Polytopes     {177}
4.6.4  Hull in Higher Dimensions     {177}
4.6.5  Exercises     {178}
5  Voronoi Diagrams     {181}
5.1  Applications: Preview     {181}
5.2  Definitions and Basic Properties     {183}
Two Sites     {184}
Three Sites     {184}
5.2.1  Halfplanes     {185}
Four Sites     {185}
Many Sites     {186}
5.2.2  Size of Diagram     {186}
5.3  Delaunay Triangulations     {188}
5.3.1  Properties of Delaunay Triangulations     {188}
5.3.2  Properties of Voronoi Diagrams     {191}
5.3.3  Exercises     {192}
5.4  Algorithms     {193}
5.4.1  Inte   of Halfplanes     {193}
5.4.2  Incremental Construction     {193}
5.4.3  Divide and Conquer     {194}
5.4.4  Fortune's Algorithm     {194}
Cones     {194}
Cone Slicing     {195}
Parabolic Front     {197}
5.4.5  Exercises     {197}
5.5  Applications in Detail     {198}
5.5.1  Nearest Neighbors     {198}
Nearest Neighbor Queries     {198}
All Nearest Neighbors     {199}
5.5.2  Triangulation maximizing the minimum angle     {199}
5.5.3  Largest Empty Circle     {200}
Centers inside the Hull     {201}
Centers on the Hull     {202}
Algorithm     {203}
5.5.4  Minimum Spanning Tree     {203}
Kruskal's algorithm     {204}
MST \subseteq {\fam \tw@ D}(P)     {204}
5.5.5  Traveling Salesperson Problem     {205}
5.5.6  Exercises     {208}
5.6  Medial Axis     {210}
5.6.1  Exercises     {213}
5.7  Connection to Convex Hulls     {214}
5.7.1  One-dimensional Delaunay triangulations     {214}
5.7.2  Two-dimensional Delaunay triangulations     {215}
5.7.3  Implications     {219}
5.7.4  Implementation of Delaunay triangulation     {219}
O(n^4) Code     {219}
3D Hull to Delaunay Triangulation: O(n^2) Code     {221}
5.7.5  Exercises     {221}
5.8  Connection to Arrangements     {224}
5.8.1  One-dimensional Voronoi Diagrams     {225}
5.8.2  Two-dimensional Voronoi Diagrams     {225}
6  Arrangements     {227}
6.1  Introduction     {227}
6.2  Combinatorics of Arrangements     {229}
6.2.1  Zone Theorem     {230}
6.2.2  Exercises     {233}
6.3  Incremental Algorithm     {234}
6.4  Three and Higher Dimensions     {235}
6.4.1  Exercises     {236}
6.5  Duality     {236}
6.5.1  Duality mapping     {237}
6.5.2  Duality Properties     {237}
6.5.3  Exercises     {240}
6.6  Higher-Order Voronoi Diagrams     {241}
6.6.1  One-Dimensional Diagrams     {241}
6.6.2  Two-Dimensional Diagrams     {244}
6.6.3  Exercises     {245}
6.7  Applications     {245}
6.7.1  k-Nearest Neighbors     {245}
6.7.2  Hidden Surface Removal     {245}
6.7.3  Aspect Graphs     {248}
6.7.5  Exercises     {250}
6.7.6  Ham Sandwich Cuts     {251}
Red-Blue Matching     {252}
Higher Dimensions     {255}
6.7.7  Exercises     {255}
7  Search and Intersection        257
7.1  Introduction     {257}
7.2  Segment-Segment Intersection     {257}
7.3  Segment-Triangle Intersection     {261}
7.3.1  Segment-Plane Inte        264
Segment-Plane Implementation     {265}
Segment-Triangle Classification     {269}
Barycentric Coordinates.     {269}
Projection to Two Dimensions.     {271}
Segment in Plane.     {274}
Classification by Volumes.     {274}
7.3.2  Exercises     {278}
7.4  Point in Polygon     {279}
7.4.1  Winding number     {279}
7.4.2  Ray crossings     {280}
7.4.3  Exercises     {284}
7.5  Point in Polyhedron     {286}
Solid Angles     {287}
Ray Crossings     {287}
Example: Cube.     {291}
Example: Nonconvex Polyhedron.     {292}
7.5.1  Analysis     {292}
7.5.2  Exercises     {293}
7.6  Intersection of Convex Polygons     {294}
7.6.1  Implementation     {298}
Special Cases     {303}
7.6.2  Exercises     {307}
7.7  Intersection of Segments     {308}
7.8  Intersection of Nonconvex Polygons     {311}
7.8.1  Exercises     {313}
7.9  Extreme Point of Convex Polygon     {314}
7.9.1  Stabbing a Convex Polygon     {316}
7.9.2  Exercises     {317}
7.10  Extremal Polytope Queries     {317}
7.10.1  Sketch of Idea     {318}
7.10.2  Independent Sets     {318}
7.10.3  Independent Sets: Properties and Algorithm     {322}
7.10.4  Construction of Nested Polytope Hierarchy     {324}
Space Requirements     {324}
Retriangulating Holes     {325}
7.10.5  Extreme Point Algorithm     {325}
Extreme Edges     {327}
7.10.6  Exercises     {330}
7.11  Planar Point Location     {332}
7.11.1  Applications     {332}
7.11.2  Independent Set Algorithm     {333}
7.11.3  Monotone Subdivisions     {333}
7.11.4  Randomized Trapezoidal Decomposition     {335}
7.11.5  Exercises     {341}
8  Motion Planning     {343}
8.1  Introduction     {343}
8.1.1  Problem Specification     {343}
8.1.2  Outline     {344}
8.2  Shortest Paths     {344}
8.2.1  Visibility Graphs     {344}
8.2.2  Constructing the Visibility Graph     {346}
8.2.3  Dijkstra's algorithm     {347}
Algorithm     {347}
Time Complexity     {349}
8.2.4  Exercises     {349}
8.3  Moving a Disk     {350}
8.3.1  Minkowski Sum     {350}
8.3.2  Conceptual Algorithm     {352}
8.4  Translating a Convex Polygon     {352}
8.4.1  Minkowski Sum Example     {352}
8.4.3  Constructing the Minkowski Sum     {354}
8.4.4  Implementation of Minkowski Convolution     {356}
8.4.5  Conceptual Motion Planning Algorithm     {362}
8.4.6  Exercises     {364}
8.5.1  Cell decomposition     {368}
Definition of a Cell     {368}
Connectivity Graph G_\theta      {368}
Critical Orientations     {370}
Connectivity graph G     {371}
8.5.2  Retraction     {371}
Voronoi diagram     {372}
Retraction     {373}
8.5.3  Complexity     {373}
8.5.4  Exercises     {374}
8.6  Robot Arm Motion     {376}
Problem Definition     {376}
History     {377}
8.6.1  Reachability: Decision     {377}
Reachability Region     {377}
8.6.2  Reachability: Construction     {380}
Linear Algorithm for n-link Reachability.     {383}
Two Kinks.     {384}
Algorithm.     {385}
8.6.3  Implementation of Link Configuration     {386}
Intersection of Two Circles     {389}
Example     {393}
8.6.4  Exercises     {394}
8.7  Separability     {395}
8.7.1  Varieties of separability     {396}
8.7.2  Separability by translation     {397}
Application     {397}
Separating segments     {398}
Separating convex polygons     {399}
Complexity     {399}
8.7.3  Reduction from Partition     {400}
8.7.4  Mimicking the Towers of Hanoi     {400}
8.7.5  Exercises     {402}
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}