Sep 20, 3:30pm, Wean 8220

Ameya Velingker, CMU

Meshing log n Dimensions in Polynomial Time

Ameya Velingker, CMU

Meshing log n Dimensions in Polynomial Time

Abstract:

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.