Stabbing Delaunay Tetrahedralizations

A Delaunay tetrahedralization of $n$ vertices is exhibited for which a straight line can pass through the interiors of $\Theta(n^2)$ tetrahedra. This solves an open problem of Amenta, who asked whether a line can stab more than $O(n)$ tetrahedra. The construction generalizes to higher dimensions: in $d$ dimensions, a line can stab the interiors of $\Theta(n^{\lceil d / 2 \rceil})$ Delaunay $d$-simplices. The relationship between a Delaunay triangulation and a convex polytope yields another result: a two-dimensional slice of a $d$-dimensional $n$-vertex polytope can have $\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.