Geometric Decompositions and Networks - Approximation Bounds and Algorithms

Sammanfattning: In this thesis we focus on four problems in computational geometry: In the first four chapters we consider the problem of covering an arbitrary polygon with simpler polygons, i.e., rectangles. We present several approximation algorithms for this problem, and also some lower bounds on the number of rectangles needed in a covering of a hole-free polygon and on the time-complexity for this and related problems. Then, we consider a generalization of the well-known Euclidean traveling salesman problem (TSP), namely the TSP with neighborhoods problem. In the TSP with neighborhoods problem we are given a collection of polygonal regions, and we seek the shortest tour that visits each neighborhood at least once. We give approximation algorithms for the problem and also show a result on the hardness of the problem. Next we turn our attention to the problem of finding a t-spanner of a complete geometric graph. The aim is to produce a sparse graph with a small number of edges and with low total weight, that is almost as "good" as a complete graph. With good we mean that for every pair of points in the graph there exists a path in the spanner graph that is at most t times longer than the distance between the two points. We present several approximation algorithms for this problem. In the final chapter of the thesis we introduce the concept of higher-order Delaunay triangulations. We give an algorithm to compute which edges can be included in a higher-order Delaunay triangulation. We show that for 1-order Delaunay triangulations, most of the criteria we study can be optimized in O(n log n) time, for example, minimizing the number of local minima, the number of local extrema, the maximum angle, area triangle, and degree of any vertex.