Math @ Duke

Publications [#235414] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Basch, J; Berg, MD; Guibas, LJ; Hershberger, J, Lower bounds for kinetic planar subdivisions,
in Fifteenth Annual Symposium on Computational Geometry,
Proceedings of the Annual Symposium on Computational Geometry
(1999),
pp. 247254
(last updated on 2018/03/20)
Abstract: We revisit the notion of kinetic efficiency for noncanonicallydefined discrete attributes of moving data, like binary space partitions and triangulations. Under very general computational models, we obtain lower bounds on the minimum amount of work required to maintain any binary space partition of moving segments in the plane or any Steiner triangulation of moving points in the plane. Such lower bounds  the first to be obtained in the kinetic context  are necessary to evaluate the efficiency of kinetic data structures when the attribute to be maintained is not canonically defined.


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

