Discrete Voronoi Refinement
Voronoi and Delaunay refinement are standard algorithmic techniques used in surface reconstruction and mesh generation in Euclidean spaces. For point sets, the resulting output is a triangulation of a superset of the points in which every triangle has angles larger than a user-defined constant. This guarantees that the total complexity is linear in the number of points (even in dimensions greater than two). These simple refinement heuristics are local updates that naturally produce asymptotically optimal size outputs. In this talk, I will discuss how one can translate the algorithms and optimality theory of Voronoi refinement to non-Euclidean spaces, specifically finite doubling metrics. I will also discuss some target applications for this theory in topological data analysis.
I am an Associate Professor of Computer Science at the North Carolina State University. My research is in geometric algorithms. I am most interested in the intersection of geometric algorithms and topological data analysis.