An Efficient Algorithm for the 2-Central Path Problem

In this paper we consider the following 2-Central Path Problem (2CPP): Given a set of m polygonal curves = {P₁,P₂,...,P_m} in the plane, find two curves P_u and P_l, called 2-central paths, that best represent all curves in . Despite its theoretical interest and a wide range of practical applications, 2CPP has not been well studied. In this paper, we first establish criteria that P_u and P_l ought to meet in order for them to best represent . In particular, we require that there exists parametrizations f_u(t) and f_l(t) (t [a,b]) of P_u and P_l respectively such that the maximum distance from {f_u(t),f_l(t)} to curves in is minimized. Then an efficient algorithm is presented to solve 2CPP under certain realistic assumptions. Our algorithm constructs P_u and P_l in O(nmlog⁴n2^α(n)α(n)) time, where n is the total complexity of (i.e., the total number of vertices and edges), m is the number of curves in , and α(n) is the inverse Ackermann f_unction. Our algorithm uses parametric search technique and is considerably faster than arrangement-related algorithms (i.e. ω(n²)) when m ≪ n as in most real applications.