Every real algebraic variety determines a Voronoi decomposition of its ambient Euclidean space.
Each Voronoi cell is a convex semialgebraic set in the normal space of the variety at a point.
We compute the algebraic boundaries of these Voronoi cells. Using intersection theory, we give a
formula for the degrees of the algebraic boundaries of Voronoi cells of curves and surfaces. We
discuss an application to lowrank matrix approximation. This is joint work with Diego
Cifuentes, Kristian Ranestad, and Bernd Sturmfels.
