Discrete Voronoi Refinement

Algorithms Seminar
Speaker Name
Don Sheehy
Date and Time
The talk will be virtual on Zoom.
The Zoom link will be emailed to CS faculty/grad students, or contact Jennifer Schmidt (jschmidt at cs.duke.edu) to request it.

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.

Short Biography

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.