A Computational Framework for Incremental Motion
David Mount
Department of Computer Science
and Institute for Advanced Computer Studies
University of Maryland

Jan 20, 2004
11-11:50 AM
Room 3530, HKUST


Abstract
--------
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.

We present a simple online protocol, through which the incremental
motion algorithm generates motion estimates.  We show that, given a
parameter epsilon > 0, the number of motion estimates generated by this
protocol has a competitive ratio of O(1/epsilon) relative to an optimal
algorithm that has full knowledge of the future motion of the points but
is required to maintain an additional epsilon-factor separation relative
to the certificate failure regions.

(Joint with N. Netanyahu, C. P. Piatko, R. Silverman, and A. Y. Wu)