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