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

Math @ Duke



Publications [#235440] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Guibas, LJ; Hershberger, J; Veach, E, Maintaining the extent of a moving point set, Discrete and Computanional Geometry, vol. 26 no. 3 (2001), pp. 353-374
    (last updated on 2017/12/10)

    Let S be a set of n moving points in the plane. We give new efficient and compact kinetic data structures for maintaining the diameter, width, and smallest area or perimeter bounding rectangle of S. If the points in S move with algebraic motions, these structures process O(n2+δ) events. We also give constructions showing that Ω(n2) combinatorial changes are possible for these extent functions even if each point is moving with constant velocity. We give a similar construction and upper bound for the convex hull, improving known results.
ph: 919.660.2800
fax: 919.660.2821

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