A practical evaluation of kinetic data structures
Julien Basch, Leonidas Guibas, Craig D. Silverstein, Li Zhang · 1997
this paper is to study and validate the use of the kinetic data structures proposed in [BGH97] in practice. The implementation and experimental evaluation of such structures brings to light several important issues which were not addressed in the original paper. For instance, KDSs implement the continuous maintenance of the function of interest through a discrete-event simulation. The calculation of the event times poses numerical difficulties which raise questions about the integrity of the structure if nearby events should happen out of order, or if the time of an event changes when recalculated. Also, the algorithmic measures for evaluating the quality of KDSs in [BGH97] are all worst-case measures, which may not reflect behavior under ordinary motions which occur in practice. It may well be that simple data structures do better in such situations. In order to study these issues, we have compared the KDSs of [BGH97] with simpler variants under various common data/motion distributions, each meant to generate a different amount of