Home Bookmarks Papers Blog

Geometric Approximation Algorithms
and
Randomized Algorithms for Planar Arrangements

Sariel Har-Peled

PhD Thesis
Tel-Aviv Univserity

The work on this thesis was carried out under the supervision of Prof. Micha Sharir


PDF
Postscript file - old ver: 170 pages.

Front page [PS]

Part I - Geometric Approximation Algorithms

1. Introduction [PS]

    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 [PS]

    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 [PS]

    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 [PS]

    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 R3
    4.4 Constructing Spatial Approximate Shortest-Path Maps in R3
    4.5 Conclusions

5. Approximating Minimum-Width Annuli and Shells [PS]

    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 [PS]

    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 [PS]

    7.1 Cuttings
    7.2 Taking a Walk in a Planar Arrangement

8. Constructing Cuttings in Theory and Practice [PS]

    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 [PS]

    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 [PS]


less old LaTeX source

Older OLD LaTeX source
You might also need style files from: style files.
Last modified: Mon Sep 21 16:56:19 CDT 2015