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_1, P2,....P_m} in the plane, find two curves P_(lt) and P_l, called 2-central paths, that best represent all curves in P. 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_(lt) 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_(lt) and P_l respectively such that the maximum distance from {f_u(t),f_l(t)} to curves in P is minimized. Then an efficient algorithm is presented to solve 2CPP under certain realistic assumptions. Our algorithm constructs P_(lt) and P_l in O(nm log~4 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~2)) when m n as in most real applications.