A near-linear algorithm for the planar segment-center problem

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(n ^1+ε), for any ε>0, improving the previous solution of Agarwalet al. 3] by nearly a factor ofO(n). Work on this paper by the second author has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.