Geometric Approximation Algorithms
and
Randomized Algorithms for Planar Arrangements

Front page

Part I - Geometric Approximation Algorithms

1 Introduction

1.1 The Approximate Euclidean Shortest-path Problem
1.2 Approximating Minimum-Width Annuli and Shells
1.3 Approximating the Minimum-Volume Bounding Box

2 Geometric Preliminaries

2.1 Notations
2.2 Approximating a Convex Polytope
2.3 Approximating Paths by a Outer Paths with Small Folding Angle
2.4 Projecting an Outer Path to a Polytope
2.5 Approximating the Diameter of a Point-Set

3 Approximate Shortest-Path Queries on a Convex Polytope

3.1 Constant Factor Approximation
3.2 eps-Approximation Algorithm for Shortest Paths

3.2.1 Answering Approximate Shortest Path Queries
3.3 Approximating the Geodesic Diameter of a Convex Polytope
3.4 Conclusions

4 Constructing Approximate Shortest Path Maps

4.1 Introduction
4.2 Approximating a distance function by a weighted Voronoi diagram
4.3 Approximate Shortest-Path Map on a Polyhedral Surface in R³
4.4 Constructing Spatial Approximate Shortest-Path Maps in R³
4.5 Conclusions

5 Approximating Minimum-Width Annuli and Shells

5.1 Introduction
5.2 Geometric Preliminaries
5.3 A (1+eps)-Approximation Algorithm in Any Dimension

5.3.1 A Strongly Polynomial eps-Approximation Algorithm for the Minimum-Width Annulus in the Plane

6 Computing Approximate Minimum Volume Bounding Boxes

6.1 Introduction
6.2 Notations and Definitions
6.3 An Efficient Approximation Algorithm
6.4 An Alternative Practical Algorithm
6.5 Experimental Results
6.6 Conclusions

Part II - Randomized Algorithms for Planar Arrangements

7 Introduction

7.1 Cuttings
7.2 Taking a Walk in a Planar Arrangement

8 Constructing Cuttings in Theory and Practice

8.1 Introduction
8.2 Incremental Randomized Construction of Cuttings

8.2.1 Cuttings by Vertical Polygons
8.3 Generating Small Cuttings - Matousek's Construction Revisited
8.4 Empirical Results

8.4.1 The Implemented Algorithms - Using Vertical Trapezoids
8.4.3 Implementation Details
8.4.4 Results - Vertical Trapezoids
8.4.5 Implementing Matousek's Construction
8.4.6 Results - Polygonal Cuttings

8.5 Conclusions

9 Taking a Walk in a Planar Arrangement

9.1 Introduction
9.2 The Algorithm
9.3 Analysis of CompZoneOnline

9.3.1 Correctness
9.3.2 Running Time

9.4 Applications

9.4.1 Computing a Level in an Arrangement of Arcs
9.4.2 ther Applications

9.5 Conclusions
9.A Appendix - Pseudo-code for Subroutines of CompZoneOnline
9.B Appendix - Taking a Walk in Ten Easy Figures

Bibliography