On 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 ₂,..., 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 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 P. 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 P (i.e., the total number of vertices and edges), m is the number of curves in P, and α(n) is the inverse Ackermann function.Our algorithm uses the parametric search technique and is faster than arrangement-related algorithms (i.e. Ω(n ²)) when m ≪ n as in most real applications.