Define a static algorithm to be an algorithm that computes some combinatorial property of its input consisting of static, i.e., non-moving, objects. In this paper, we describe a technique for syntactically transforming static algorithms into kinetic algorithms, which compute the statically computed property under motion, a la kinetic data structures. Based on the properties of the transformation technique, we give an algorithm for performing robust motion simulations with fixed-precision floating-point arithmetic. To evaluate the practical effectiveness of the approach, we implement a library for performing the transformation, transform a number of algorithms and give a detailed experimental evaluation. The results show that the technique makes it easy to implement robust kinetic algorithms and delivers good performance in practice.

17 pages

*Toyota Technological Institute of Chicago
**Stanford University

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu