PLANAR GEOMETRIC LOCATION-PROBLEMS

Authors
AGARWAL PK SHARIR M
Citation
Pk. Agarwal et M. Sharir, PLANAR GEOMETRIC LOCATION-PROBLEMS, Algorithmica, 11(2), 1994, pp. 185-195
Citations number
13
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
11
Issue
2
Year of publication
1994
Pages
185 - 195
Database
ISI
SICI code
0178-4617(1994)11:2<185:PGL>2.0.ZU;2-D
Abstract
We present an O(n(2) log(3) n) algorithm for the two-center problem, i n which we are given a set S of n points in the plane and wish to find two closed disks whose union contains S so that the larger of the two radii is as small as possible. We also give an O(n(2) log(5) n) algor ithm for solving the two-line-center problem, where we want to find tw o strips that cover S whose maximum width is as small as possible. The best previous solutions of both problems require O(n(3)) time.