A FASTER ALGORITHM FOR THE 2-CENTER DECISION PROBLEM

Authors
HERSHBERGER J
Citation
J. Hershberger, A FASTER ALGORITHM FOR THE 2-CENTER DECISION PROBLEM, Information processing letters, 47(1), 1993, pp. 23-29
Citations number
7
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
47
Issue
1
Year of publication
1993
Pages
23 - 29
Database
ISI
SICI code
0020-0190(1993)47:1<23:AFAFT2>2.0.ZU;2-6
Abstract
The planar two-center decision problem can be stated as follows: Given a set of n points in the plane and two radii r1 and r2, determine whe ther the points can be covered by two disks of the specified radii. Th is note presents an O(n2) algorithm for the problem, which improves th e previous O(n2 log n) algorithm.