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 F P a t h V D ( 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 F P a t h V D ( Q ) directly related to P. The running time of our approach is thus O ( ( H + m k + n + s ) log m log 2 n ) which is bounded by O ( n 2 2 α ( 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 F P a t h V D ( Q ) by the central path algorithm, and H is the number of intersections between the visited portion of F P a t h V D ( Q ) and V D ( P i ) ( i = 1, 2, …, m ).

Authors

• Yongding Zhu
• Jinhui Xu Department of Computer Science and Engineering, State University of New York at Buffalo, NY, USA

Keywords

• Central path
• Farthest-path Voronoi diagram
• Output sensitive
• Computational geometry