Instance Parameters: How to Efficiently Use, Compute and Approximate them

Abstract

In this thesis we study six problems, two graph problems and four computational geometry problems. In the first four chapters we consider the problem of adding $k$ shortcut edges to a metric graph so that the radius of the augmented graph is minimized. We consider the general problem and several variants of the problem. Approximation algorithm is given for the general problem and exact algorithms are given for more restricted variants of the problem. In Chapter~\ref{beer_distance_chapter} we consider the shortest beer path query problem in beer digraphs with bounded treewidth. We also consider shortest beer path queries in a dynamic setting where the weight of an edge can be changed over time. Then, we consider computing the packedness of polygonal curves in $\R^d$. The packedness of a curve measures how congested the curve is. For many well-behaved curves, the packedness is small. We give approximation algorithms for computing the packedness of polygonal curves in $\R^d$. Next we study the problem of separated red-blue center clustering. The line-constrained version of the problem requires that all (red and blue) centers lie on a line. We give improved algorithms for the separated red-blue center clustering problem and the line-constrained version of the problem. In Chapter~\ref{center_segment_chapter} we give a linear time algorithm for finding the center segment of a point set $P$. The center segment of $P$ is a segment bounded by two points in $P$ such that the maximum distance from a point in $P$ to it is minimized. Finally we study the spanning ratio of rectangle Delaunay triangulation. In Chapter~\ref{rectangle_Delaunay_chapter} we prove that Delaunay triangulations constructed using rectangles with aspect ratio $\A$ have spanning ratio at most $\sqrt{2} \sqrt{1+\A^2 + \A \sqrt{\A^2 + 1}}$, which matches the known lower bound.