TY - GEN

T1 - Efficient algorithm for the Euclidean two-center problem

AU - Jaromczyk, Jerzy W.

AU - Kowaluk, Miroslaw

PY - 1994

Y1 - 1994

N2 - We present a new algorithm for the two-center problem: 'Given a set S of n points in the real plane, find two closed discs whose union contains all of the points and the radius of the larger disc is minimized.' An almost quadratic O(n2 log n) solution is given. The previously best known algorithms for the two-center problem have time complexity O(n2log3n). The solution is based on a new geometric characterization of the optimal discs and on a searching scheme with so-called lazy evaluation. The algorithm is simple and does not assume general position of the input points. The importance of the problem is known in various practical applications including transportation, station placement, and facility location.

AB - We present a new algorithm for the two-center problem: 'Given a set S of n points in the real plane, find two closed discs whose union contains all of the points and the radius of the larger disc is minimized.' An almost quadratic O(n2 log n) solution is given. The previously best known algorithms for the two-center problem have time complexity O(n2log3n). The solution is based on a new geometric characterization of the optimal discs and on a searching scheme with so-called lazy evaluation. The algorithm is simple and does not assume general position of the input points. The importance of the problem is known in various practical applications including transportation, station placement, and facility location.

UR - http://www.scopus.com/inward/record.url?scp=0028015214&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028015214&partnerID=8YFLogxK

U2 - 10.1145/177424.178038

DO - 10.1145/177424.178038

M3 - Conference contribution

AN - SCOPUS:0028015214

SN - 0897916484

SN - 9780897916486

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 303

EP - 311

BT - Proceedings of the Annual Symposium on Computational Geometry

T2 - Proceedings of the 10th Annual Symposium on Computational Geometry

Y2 - 6 June 1994 through 8 June 1994

ER -