THE DISCRETE 2-CENTER PROBLEM

Authors
AGARWAL PK SHARIR M WELZL E
Citation
Pk. Agarwal et al., THE DISCRETE 2-CENTER PROBLEM, Discrete & computational geometry, 20(3), 1998, pp. 287-305
Citations number
15
Categorie Soggetti
Computer Science Theory & Methods",Mathematics,"Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
20
Issue
3
Year of publication
1998
Pages
287 - 305
Database
ISI
SICI code
0179-5376(1998)20:3<287:>2.0.ZU;2-S
Abstract
We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of s mallest possible radius, centered at two points of P, whose union cove rs P. Our algorithm runs in time O(n(4/3) log(5) n).