TY - CONF
T1 - A computational framework for incremental motion
T2 - Proceedings of the twentieth annual symposium on Computational geometry
Y1 - 2004
A1 - Mount, Dave
A1 - Netanyahu,Nathan S.
A1 - Piatko,Christine D.
A1 - Silverman,Ruth
A1 - Wu,Angela Y.
KW - competitive analysis
KW - incremental motion
KW - kinetic data structures
AB - We propose a generic computational framework for maintaining a discrete geometric structure defined by a collection of static and mobile objects. We assume that the mobile objects move incrementally, that is, in discrete time steps. We assume that the structure to be maintained is a function of the current locations of the mobile and static objects (independent of their prior motion). Unlike other models for kinetic computation, we place no restrictions on the motion nor on its predictability.In order to handle unrestricted incremental motion, our framework is based on the coordination of two computational entities. The first is the incremental motion algorithm. It is responsible for maintaining the structure and a set of certificates, or conditions, that prove the structure's correctness. The other entity, called the motion processor, is responsible for handling all the low-level aspects of motion, including computing and/or tracking the motion of the mobile objects, answering queries about their current positions and velocities, and validating that the object motions satisfy simple motion estimates, which are generated by the incremental motion algorithm. Computational efficiency is measured in terms of the number of interactions between these two entities.
JA - Proceedings of the twentieth annual symposium on Computational geometry
T3 - SCG '04
PB - ACM
CY - New York, NY, USA
SN - 1-58113-885-7
UR - http://doi.acm.org/10.1145/997817.997849
M3 - 10.1145/997817.997849
ER -