| |
Kinetic data structures provide a framework for computing
combinatorial properties of continuously moving objects. Although
kinetic data structures for many problems have been proposed, some
difficulties remain in devising and implementing them especially
robustly. One set of difficulties stem from the required update
mechanisms used for processing certificate failures---devising
efficient update mechanisms can be difficult, especially for
sophisticated problems such as those in 3D. Another set of
difficulties arise due to the strong assumption in the framework that
the update mechanism is invoked with a single event. This requires
sorting the events precisely using exact arithmetic, which is
expensive. This assumption also makes it difficult to deal with
simultaneous events that arise due to degeneracies or due to intrinsic
properties of the kinetized algorithms. In this paper, we apply
advances on self-adjusting computation to provide a robust motion
simulation technique that combines kinetic event-based scheduling and
the classic idea of fixed-time sampling. The idea is to divide time
into a lattice of fixed-size intervals and identify and process events
at the resolution of an interval. We apply the approach to the
problem of kinetic maintenance of convex hulls in 3D, a problem that
has been open since 90's. We evaluate the effectiveness of the
proposal experimentally. Using the approach, we are able to run
simulations consisting of thousands of points robustly and
efficiently.
|