Jorge L. Vittes

The kinetic convex hull problem asks for maintaining the smallest convex polygon of a set of moving points - this polygon is called a convex hull. I present a new technique for maintaining the kinetic convex hull problem. This technique enables one to make any convex hull algorithm kinetic semi-automatically using a simple library. The idea is to determine the failure times of all tests involving points and update the result at these times. The result is updated via adaptive computing. Adaptive computing represents a computation with a dependency graph and updates the result when changes occur.