Lower bounds for kinetic planar subdivisions

P.K. Agarwal, J. Basch, M. Berg, de, L.J. Guibas, J. Hershberger

    Research output: Contribution to journalArticleAcademicpeer-review

    12 Citations (Scopus)


    We revisit the notion of kinetic efficiency for noncanonically defined discrete attributes of moving data, like binary space partitions and triangulations. Under reasonable 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.
    Original languageEnglish
    Pages (from-to)721-733
    JournalDiscrete and Computational Geometry
    Issue number4
    Publication statusPublished - 2000


    Dive into the research topics of 'Lower bounds for kinetic planar subdivisions'. Together they form a unique fingerprint.

    Cite this