Lower bounds for kinetic planar subdivisions

We revisit the notion of kinetic efficiency for noncanonically defined disc rete attributes of moving data, like binary space partitions and triangulat ions. Under reasonable computational models, we obtain lower bounds on the minimum amount of work required to maintain any binary space partition of m oving segments in the plane or any Steiner triangulation of moving points i n the plane. Such lower bounds-the first to be obtained in the kinetic cont ext-are necessary to evaluate the efficiency of kinetic data structures whe n the attribute to be maintained is not canonically defined.