| Given a weighted polygonal subdivision R in the plane or space, we consider three geometric optimization problems in R. First, we address the Frechet distance problem in weighted regions. The Frechet distance is a similarity metric for continuous curves. We discuss two versions of the Frechet distance problem in weighted regions in R2 . In the first one, the distance between two points is the weighted length of the line segment joining the points. In the second one, the distance between two points is the length of the shortest path between the points. In both cases, we give algorithms for finding a (1 + epsilon)-factor approximation of the Frechet distance between two polygonal curves. We also consider the Frechet distance between two polygonal curves among polyhedral obstacles in R3 (a 1/infinity weighted region problem) and present a (1 + epsilon)-factor approximation algorithm.;Second, we consider the line facility location problem in weighted regions. That is, given a set of fixed points in a weighted planar subdivision R, the problem seeks to find a facility L, which is a line segment, such that each fixed point is connected to L via an orthogonal link and some cost function associated with the facility location is minimized. We consider three versions of this problem, depending on how the cost function is defined. For the first version (P1), we want to minimize the sum of weighted length of orthogonal links. For the second version (P2), we want to minimize the weighted length of L. The third version (P3) is the combination of the first two versions. That is, we want to minimize the sum of the weighted length of all orthogonal links and L. We show that each version of this problem can be reduced to a number of 1-variable optimization problems, which can be solved by either computing the exact roots of polynomials or by approximation algorithms. The feasible domain for each subproblem is an arc or a line segment in the dual plane.;Finally, we address a 1/infinity weighted region problem in R3 , which we refer to as the approximate point-to-face shortest path problems. The problem is defined as follows: Given a set of polyhedral obstacles with a total of n vertices, a source point s, and a destination face f of some obstacle in the input, find a path between s and f that avoids the interior of the obstacles and has length at most (1 + epsilon) times the length of the shortest obstacle avoiding path between s and f. |
