Path optimization in combined metrics

Path optimization problems have been extensively studied due to their numerous applications. This dissertation investigates path optimization problems, where the objective function is a combined metric derived from combining more than one optimality criterion. In particular, we consider a graph theoretic problem known in the literature as the quickest path problem, and a geometric problem in the Euclidean plane. The former involves a data transmission network in which the cost of transmission is measured in terms of both the transmission setup time and the transmission rate between nodes along the transmission path. The latter encompasses a new class of problems and is defined as follows.; Path planning in a polygonal domain of weighted vertices: Given a polygonal domain, where vertices are weighted with a non-negative weight, a source point s and a destination point t, find an obstacle-avoiding straight line path from s to t that only turns at obstacle vertices, such that the cost of the path is minimized, where the cost of a path is defined to be the length plus the sum of the weights of the vertices of the path.; In this dissertation we consider the special case where weights are restricted to 0 and infinity and the polygonal domain is a simple polygon. Vertices of infinite weight are called forbidden; a feasible path is not allowed to turn on forbidden vertices. We investigate the geometric properties of shortest paths in a simple polygon of n vertices in the presence of k forbidden vertices, and derive an {dollar}O(ksp2n{dollar} log n) time algorithm. Tackling this problem, a well known geometric structure, the geodesic Voronoi diagram of k point sites in a simple polygon of n vertices, turned out to be of particular value. We provide an O((n + k) log(n + k))-time algorithm to construct this diagram improving upon the previously best known result. Another contribution is an O((n + k) log n)-time algorithm to compute the set of shortest paths connecting k source-destination pairs of points on the boundary of a simple polygon, such that they are pairwise noncrossing. The result is used by the algorithm to compute shortest paths in a simple polygon in the presence of forbidden vertices.