Efficient algorithm for the Euclidean two-center problem

Jerzy W. Jaromczyk, Miroslaw Kowaluk

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

40 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the Annual Symposium on Computational Geometry
Pages303-311
Number of pages9
DOIs
StatePublished - 1994
EventProceedings of the 10th Annual Symposium on Computational Geometry - Stony Brook, NY, USA
Duration: Jun 6 1994Jun 8 1994

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Conference

ConferenceProceedings of the 10th Annual Symposium on Computational Geometry
CityStony Brook, NY, USA
Period6/6/946/8/94

ASJC Scopus subject areas

  • Software
  • Geometry and Topology
  • Safety, Risk, Reliability and Quality
  • Chemical Health and Safety

Fingerprint

Dive into the research topics of 'Efficient algorithm for the Euclidean two-center problem'. Together they form a unique fingerprint.

Cite this