A practical evaluation of kinetic data structures

In many applications of computational geometry to model ing objects and processes in the physical world the partici pating objects are in a state of continuous change Motion is the most ubiquitous kind of continuous transformation but others such as shape deformation are also possible In a recent paper Basch Guibas and Hershberger BGH pro posed the framework of kinetic data structures KDSs as a way to maintain in a completely on line fashion desirable information about the state of a geometric system in contin uous motion or change They gave examples of kinetic data structures for the maximum of a set of changing numbers and for the convex hull and closest pair of a set of moving points in the plane The KDS framework allows each object to change its motion at will according to interactions with other moving objects the environment etc We implemented the KDSs described in BGH as well as some alternative methods serving the same purpose as a way to validate the kinetic data structures framework in practice In this note we report some preliminary results on the maintenance of the convex hull describe the experi mental setup compare three alternative methods discuss the value of the measures of quality for KDSs proposed by BGH and highlight some important numerical issues