Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235389] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, P; Sharir, M, Planar geometric location problems, Algorithmica (New York), vol. 11 no. 2 (1994), pp. 185-195
    (last updated on 2017/12/11)

    Abstract:
    We present an O(n2 log3 n) algorithm for the two-center 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 two-line-center 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 27708-0320