Math @ Duke

Publications [#235389] of Pankaj K. Agarwal
Papers Published
 Agarwal, P; Sharir, M, Planar geometric location problems,
Algorithmica (New York), vol. 11 no. 2
(1994),
pp. 185195
(last updated on 2018/08/21)
Abstract: We present an O(n2 log3 n) algorithm for the twocenter problem, in 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 possible. We also give an O(n2log4n) algorithm for solving the twolinecenter problem, where we want to find two strips that cover S whose maximum width is as small as possible. The best previous solutions of both problems require O(n3) time.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

