Lower bounds for kinetic planar subdivisions

Journal Article (Journal Article)

We revisit the notion of kinetic efficiency for non-canonically-defined 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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Basch, J; de Berg, M; Guibas, LJ; Hershberger, J

Published Date

  • January 1, 1999

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 247 - 254

Digital Object Identifier (DOI)

  • 10.1145/304893.304961

Citation Source

  • Scopus