The ACO Seminar (2012-2013)

We study the problem of generating a conforming Delaunay mesh with quality for point sets in high-dimension. Previously, most meshing algorithms were designed for 2 or 3 dimensions. The talk will motivate the discussion of meshing in higher-dimensional settings and give an overview of existing algorithms. Finally, we propose a new algorithm which produces the 1-dimensional skeleton of a Delaunay mesh with guaranteed size and quality. Our comparison-based algorithm runs in time O(2^O(d) * (n log n + m)), where n is the input size, m is the output point set size, and d is the ambient dimension.