Nederlandse Organisatie voor Wetenschappelijk Onderzoek (NWO)
The notion of Voronoi diagram is central for convex and computational geometry. Its analog in differential geometry is the notion of cut locus. Local structure of a typical cut locus (near its non-boundary points) is similar to local structure of a typical Voronoi diagram. For example, a typical cut locus in dimension 3 consists of smooth two-dimensional strata, triple lines, and isolated vertices whose neighborhoods in a cut locus look like the cone over the 1-skeleton of a tetrahedron. Spines are widely used in algorithmic topology for encoding 3-manifolds, for processing the manifolds by different algorithms, and for computing their invariants (e.g. Turaev-Viro invariants). In principle, spines can be regarded as cut loci for suitable Riemannian metrics. Surprisingly, this simple idea has not been extensively explored beforehand. There are three promising directions of our project. First, we will study cut loci in 3-dimensional Riemannian manifolds as a natural generalization of Voronoi diagrams in Euclidean space. The existing generalizations usually involve a somewhat artificial from mathematical point of view (though natural for computer science) choice of metric, for example, Manhattan metric, without replacing the underlying affine space by a manifold.