ISSN:
1432-0541
Keywords:
Facility location
;
Parametric searching
;
Duality
;
Planar arrangements
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We present anO(n 2 log3 n) algorithm for the two-center problem, in which we are given a setS ofn points in the plane and wish to find two closed disks whose union containsS so that the larger of the two radii is as small as possible. We also give anO(n 2 log5 n) algorithm for solving the two-line-center problem, where we want to find two strips that coverS whose maximum width is as small as possible. The best previous solutions of both problems requireO(n 3) time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01182774
Permalink