On the central path problem
In this paper we consider the following Central Path Problem (CPP): Given a set of m arbitrary (i.e., non-simple) polygonal curves Q = {P-1, P-2, ... , P-m} with m >= 2 in 2D space, find a curve P, called a central path, which minimizes the maximum distance (measured by the directed Hausdorff distance) to all curves in Q and is the locus of the center of minimal spanning disk of Q. For the CPP problem, a direct approach is to first construct the farthest-path Voronoi diagram FPathVD(Q) of Q and then derive the central path from it, which could be rather costly. In this paper, we present a novel approach which computes the central path in an "output-sensitive" fashion. Our approach sweeps a minimal spanning disk through Q and computes only a partial structure of the FPathVD(Q) directly related to P. The running time of our approach is thus O((H + mk + n + s) log m log(2) n) which is bounded by 0(n(2)2(alpha(n))) log n) in the worst case, where n is the size of Q, s the total number of self-intersections of each individual curve in Q, k is the size of the visited portion of FPathVD(Q) by the central path algorithm, and H is the number of intersections between the visited portion of FPathVD(Q) and VD(Pi) (i = 1, 2, ... , m). (C) 2013 Elsevier B.V. All rights reserved.
central path farthest-path voronoi diagram output sensitive computational geometry