A near-linear algorithm for the planar segment center problem
Alon Efrat, Micha Sharir · 1994
LetP be a set ofn points in the plane and lete be a segment of fixed length. The segment-center problem is to find a placement ofe (allowing translation and rotation) which minimizes the maximum euclidean distance frome to the points ofP. We present an algorithm that solves the problem in timeO(n1+e), for any e>0, improving the previous solution of Agarwalet al. [3] by nearly a factor ofO(n).