1994 · 48 citations · 8 references
ComputingComputer ScienceTransportation PlanningAlgorithmsFacility LocationOptimizationApproximation AlgorithmsFacility SitingGeometric OptimizationLocation-allocation AnalysisMultiple-facility LocationEuclidean Facility LocationFacility Location ApproximationLazy EvaluationPolynomial Time ComplexityService Station PlacementStation Point Placement
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(n2logn) 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.
8
Algorithms in Combinatorial Geometry.
Jacob E. Goodman, Herbert Edelsbrunner · American Mathematical Monthly · 1989 · 1.8K citations
Michael Ian Shamos, Dan Hoey · 1975 · 1.1K citations
The Planar Two-Center and Two-Median Problems
Zvi Drezner · Transportation Science · 1984 · 120 citations
John Hershberger, Subhash Suri · Journal of Algorithms · 1991 · 93 citations