Computational Geometry in C (2nd Ed.)


Table of Contents (Detailed)

(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.3  Gift Wrapping     {79}
   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  Additional 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.1  Gift Wrapping     {129}
      4.2.2  Divide and Conquer     {129}
         Discarding hidden faces     {132}
         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}
            Head pointers.     {141}
            Basic List Processing.     {142}
             |structs|: Full Detail.     {142}
      4.3.2  Example: Cube     {145}
             |main|.     {145}
             |ReadVertices|.     {145}
             |DoubleTriangle|.     {145}
             |ConstructHull|.     {149}
             |AddOne|.     {149}
             |VolumeSign|.     {153}
             |AddOne|: Cube Example.     {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.3  Quad-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}
   4.7  Additional 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.4  Smallest Polytope Shadow     {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}
   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.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}
         Linking Polytopes     {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}
         Spreading Paint     {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.2  Minkowski Addition     {353}
      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  Moving a Ladder     {365}
      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}
         Annulus Radii     {379}
      8.6.2  Reachability: Construction     {380}
         2-link Reachability     {380}
         3-link Reachability     {381}
         n-link Reachability     {383}
            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}