ISSN:
1432-0541
Schlagwort(e):
Facility location
;
Parametric searching
;
Duality
;
Planar arrangements
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01182774
Permalink
