COMPUTATIONAL GEOMETRY

By T. LANIU

CONTENTS COMPUTATIONAL GEOMETRY AN EXAMPLE: CONVEX HULLS DEGENERACIES AND ROBUSTNESS APPLICATION DOMAINS NOTES AND COMMENTS EXERCISES LINE SEGMENT INTERSECTION THE DOUBLY-CONNECTED EDGE LIST COMPUTING THE OVERLAY OF TWO SUBDIVISIONS BOOLEAN OPERATIONS POLYGON TRIANGULATION GUARDING AND TRIANGULATIONS PARTITIONING A POLYGON INTO MONOTONE PIECES TRIANGULATING A MONOTONE POLYGON LINEAR PROGRAMMING THE GEOMETRY OF CASTING HALF-PLANE INTERSECTION INCREMENTAL LINEAR PROGRAMMING RANDOMIZED LINEAR PROGRAMMING UNBOUNDED LINEAR PROGRAMS 4 6* LINEAR PROGRAMMING IN HIGHER DIMENSIONS 4 7* SMALLEST ENCLOSING DISCS ORTHOGONAL RANGE SEARCHING 1-DIMENSIONAL RANGE SEARCHING KD-TREES RANGE TREES HIGHER-DIMENSIONAL RANGE TREES GENERAL SETS OF POINTS 5 6* FRACTIONAL CASCADING POINT LOCATION POINT LOCATION AND TRAPEZOIDAL MAPS A RANDOMIZED INCREMENTAL ALGORITHM DEALING WITH DEGENERATE CASES 6 4* A TAIL ESTIMATE VORONOI DIAGRAMS DE?NITION AND BASIC PROPERTIES COMPUTING THE VORONOI DIAGRAM VORONOI DIAGRAMS OF LINE SEGMENTS FARTHEST-POINT VORONOI DIAGRAMS ARRANGEMENTS AND DUALITY COMPUTING THE DISCREPANCY DUALITY ARRANGEMENTS OF LINES LEVELS AND DISCREPANCY DELAUNAY TRIANGULATIONS TRIANGULATIONS OF PLANAR POINT SETS THE DELAUNAY TRIANGULATION COMPUTING THE DELAUNAY TRIANGULATION THE ANALYSIS 9 5* A FRAMEWORK FOR RANDOMIZED ALGORITHMS 10 MORE GEOMETRIC DATA STRUCTURES WINDOWING 10 1 INTERVAL TREES 10 2 PRIORITY SEARCH TREES 10 3 SEGMENT TREES 10 4 NOTES AND COMMENTS 10 5 EXERCISES 11 CONVEX HULLS MIXING THINGS 11 1 THE COMPLEXITY OF CONVEX HULLS IN 3-SPACE 11 2 COMPUTING CONVEX HULLS IN 3-SPACE 11 3* THE ANALYSIS 11 4* CONVEX HULLS AND HALF-SPACE INTERSECTION 11 5* VORONOI DIAGRAMS REVISITED 11 6 NOTES AND COMMENTS 11 7 EXERCISES 12 BINARY SPACE PARTITIONS THE PAINTER’S ALGORITHM 12 1 THE DE?NITION OF BSP TREES 12 2 BSP TREES AND THE PAINTER’S ALGORITHM 12 3 CONSTRUCTING A BSP TREE 12 4* THE SIZE OF BSP TREES IN 3-SPACE 12 5 BSP TREES FOR LOW-DENSITY SCENES 12 6 NOTES AND COMMENTS 12 7 EXERCISES 13 ROBOT MOTION PLANNING GETTING WHERE YOU WANT TO BE 13 1 WORK SPACE AND CON?GURATION SPACE 13 2 A POINT ROBOT 13 3 MINKOWSKI SUMS 13 4 TRANSLATIONAL MOTION PLANNING 13 5* MOTION PLANNING WITH ROTATIONS 13 6 NOTES AND COMMENTS 13 7 EXERCISES 14 QUADTREES NON-UNIFORM MESH GENERATION 14 1 UNIFORM AND NON-UNIFORM MESHES 14 2 QUADTREES FOR POINT SETS 14 3 FROM QUADTREES TO MESHES 14 4 NOTES AND COMMENTS 14 5 EXERCISES 15 VISIBILITY GRAPHS FINDING THE SHORTEST ROUTE 15 1 SHORTEST PATHS FOR A POINT ROBOT 15 2 COMPUTING THE VISIBILITY GRAPH 15 3 SHORTEST PATHS FOR A TRANSLATING POLYGONAL ROBOT 15 4 NOTES AND COMMENTS 15 5 EXERCISES 16 SIMPLEX RANGE SEARCHING WINDOWING REVISITED 16 1 PARTITION TREES 16 2 MULTI-LEVEL PARTITION TREES 16 3 CUTTING TREES 16 4 NOTES AND COMMENTS 16 5 EXERCISES BIBLIOGRAPHY