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

Math @ Duke



Publications [#235594] of Pankaj K. Agarwal

Papers Published

  1. Varadarajan, KR; Agarwal, PK, Linear approximation of simple objects, Information Processing Letters, vol. 62 no. 2 (1997), pp. 89-94
    (last updated on 2017/12/12)

    Let P = {P1, P2, . . . , Pm} be a set of m convex polygons in the plane with a total number of n vertices, and for 1 ≤ i ≤ m, let wi ∈ℝ+ be a weight associated with Pi. The weighted distance between a line l and a polygon Pi is given by d(l, Pi) = minp∈Pi,q∈l d(p, q).wi, where d(p, q) is the Euclidean distance between p and q. We want to compute a line l that minimizes the maximum distance between l and the polygons of P. We present an O(nα(n) log3 n)-time algorithm to compute such a line. We also give an O(n2+ε)-time algorithm, where ε is an arbitrarily small positive constant, to solve the three dimensional version of this problem; here, P is a set of convex polytopes in ℝ3, and we want to compute a plane h that minimizes the maximum weighted distance between h and the polytopes. © 1997 Published by Elsevier Science B.V.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320