Optimization problems in weighted regions
Ovidiu Daescu, James Dean Palmer · 2006
In this dissertation we study several shortest path problems in weighted polygonal subdivisions of the plane using the weighted distance metric. Our contributions can be divided into one of three broadly defined but strongly related problem areas: 1-Link Shortest Paths. We present a polynomial time result for computing a minimum separation (an optimal 1-link) between two regions. We also describe two 1-link approximation techniques. The first technique is based on a prune-and-search scheme that divides the problem space into a series of subproblems. These subproblems are recursively eliminated or further subdivided based on the computation of upper and lower bounds for a solution contained in that subproblem. The second technique we consider is based on computing optimal solutions for a special sum-of-fractionals (SOF) problem. We experimentally compare these two techniques using the software, LINKSOLVER, that we have developed for solving 1-link problems. k-Link Shortest Paths. Optimal 1-link paths become the basis for several algorithms we develop for approximating k-link paths. We prove structural properties of optimal k-link paths and utilize these results to obtain approximation algorithms that yield a path having O(k) links and weighted length at most (1 + e) times the weighted length of an optimal k-link path, for any fixed e > 0. We develop four approximation algorithms with different complexity characteristics and bounds on the number of approximating links. Our best theoretical result (in terms of the number of approximating links) finds an approximating path with at most 2k - 1 links. We experimentally compare these techniques using the software, k-L INKSOLVER, that we have developed for solving k-link problems. Optimal Weighted Bridges. Finally, we consider an optimal weighted bridge between two regions. An optimal weighted bridge is a special case of the shortest path problem where we are given two disjoint convex polygons P and Q in a weighted subdivision. A weighted bridge, Bw, is a path from a point p ∈ P to a point q ∈Q that connects P and Q such that the sum of the weighted length of Bw, and the maximum weighted distance from any point in P to p and from any point in Q to q is minimized. The goal is to compute an optimal weighted bridge between P and Q. To this end, we describe 2-factor and (1 + e)-factor approximation schemes for finding optimal 1-link weighted bridges between a pair of convex polygons. We also show how these techniques can be extended to k-link weighted bridges and weighted bridges where the number of links is unrestricted.