Kinetic Algorithms via Self-Adjusting Computation

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, à 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