Fixed-Parameter Algorithms for Optimal Convex Partitions and Other Results

Sammanfattning: In this thesis I study two-dimensional geometric optimization problems for which it is difficult to find efficient, exact, deterministic algorithms. All known solutions to these problems require time that is exponential in the total size of the input. The work done in this thesis is a contribution to the research directed at attacking and coping with such NP hard problems in computational geometry. A promising way to attack and cope with such problems is to find an algorithm that is exponential in the size of only one input parameter and polynomial in the size of all other input parameters. Such an algorithm is called a fixed parameter algorithm, because if we fix the single troublesome input at any one value, the problem can be solved efficiently (i.e.in polynomial time). In this thesis, I give algorithms based on this idea. Generally, the input I work with has n vertices and I choose the number k of vertices lying in the interior of the boundary of the input as the fixed parameter. Based on this idea the results in this thesis include algorithms for the minimum weight triangulation problem, the minimum weight convex partition problem, and the minimum number convex partition problem: I present four fixed parameter algorithms for finding the minimum weight triangulation of a simple polygon with n-k vertices on the perimeter and k vertices in the interior (hole vertices), that is, or a total of n vertices. All four algorithms have been implemented in Java and I report results of experiments carried out with these implementations. For the minimum weight and minimum number convex partition problem I present fixed parameter algorithms for a convex polygon with n k vertices on the perimeter and k vertices in the interior (hole vertices). However, the results for these two problems also hold for the more general case where the input is an n-vertex planar straight line graph and k is the total number of holes and/or reflex vertices inside the convex hull. For the special case of the minimum weight convex partition problem of a convex polygon with a single hole vertex (the so-called local minimum weight convex partition problem), I present an optimal algorithm and an approximation algorithm. In addition to the above closely connected results, this thesis presents results on the following related subjects: I show bounds on optimally triangulating connected subsets of the minimum weight convex partition of simple polygons and points in the plane. I consider the minimum line covering problem, which is also known to be NP-hard. I give exact and approximate algorithms and a lower time bound for restricted variants of this problem. Finally, I discuss minimum spanning trees with bi chromatic vertices. I present tight upper bounds on the maximum degree of a node in the color conforming minimum weight spanning tree and discuss bounds on the total length of the edges.