A NEAR-LINEAR ALGORITHM FOR THE PLANAR 2-CENTER PROBLEM

Authors
SHARIR M
Citation
M. Sharir, A NEAR-LINEAR ALGORITHM FOR THE PLANAR 2-CENTER PROBLEM, Discrete & computational geometry, 18(2), 1997, pp. 125-134
Citations number
17
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
18
Issue
2
Year of publication
1997
Pages
125 - 134
Database
ISI
SICI code
0179-5376(1997)18:2<125:ANAFTP>2.0.ZU;2-W
Abstract
We present an O (n log(9) n)-time algorithm for computing the 2-center of a set S of n points in the plane (that is, a pair of congruent dis ks of smallest radius whose union covers S), improving the previous O( n(2) log n)-time algorithm of [10].