View Related Documents

Abstract

A Delaunay tetrahedralization of nn vertices is exhibited for which a straight line can pass through the interiors of Q(n2)\Theta(n^2) tetrahedra. This solves an open problem of Amenta, who asked whether a line can stab more than O(n)O(n) tetrahedra. The construction generalizes to higher dimensions: in dd dimensions, a line can stab the interiors of Q(néd / 2 ù)\Theta(n^{\lceil d / 2 \rceil}) Delaunay dd-simplices. The relationship between a Delaunay triangulation and a convex polytope yields another result: a two-dimensional slice of a dd-dimensional nn-vertex polytope can have Q(nëd / 2 û)\Theta(n^{\lfloor d / 2 \rfloor}) facets. This last result was first demonstrated by Amenta and Ziegler, but the construction given here is simpler and more intuitive.

Delaunay triangulation - Delaunay tetrahedralization

Fulltext Preview

Image of the first page of the fulltext document