Deterministic Volume Approximation of Polytopes

Abstract

Computing the volume of a polytope is an important longstudied question, with applications ranging from combinatorics to machine learning. While there are numerous randomized algorithms that efficiently approximate the volume, no deterministic algorithm is currently known to exist. This is part of a fundamental question in algorithms: when is randomness truly needed? We investigate whether the notion of chaos can be a substitute for randomness in this setting. There is a key distinction to be made here between chaos and randomness. Given the initial state of a system, we cannot predict the future state of a random process. On the other hand, a chaotic one is fully deterministic, although sensitive to initial conditions. That is, any small change in initial conditions will result in vastly different outcomes. Essentially all current methods for volume approximation rely on being able to sample uniformly from the body, with randomized algorithms doing this via random walks. Instead, we aim to create a deterministic dynamical billiard system that will uniformly cover the polytope. In particular, we consider the trajectory created by the free motion of a point particle inside the polytope with mirror-like reflections off the boundary. Additionally, we add a slight concave curvature to the facets which allows for a greater dispersion of the trajectory