Stabbing numbers of triangulations

[Nina Amenta]

Jonathan Shewchuk asks: 

- Consider a line passing through a tetrahedralization.  What is the
  (asymptotically) largest number of tetrahedra the line can intersect?
  If it's o(n^2), is there a proof?  If it's Theta(n^2), is there an
  example?

It's Theta(n^2), as a corollary of G"unter & my Deformed Products
paper (aka Shadows and Slices). We showed that the intersection of
a 2-plane H with the convex hull V of n vertices in R^4 can be a 
polygon G with O(n^2) faces. Each face of G is the intersection of
H with a 3-face of V. 

Now consider projecting V to a 3-plane along a line contained in
H. The projection of H becomes a line. The projection of each 3-face
intersected by H becomes a tetrahedraon in either the projection of
the upper or lower hull of V. One or the other of these must have
O(n^2) tetrahedra intersecting the line corresponding to H. 


- How about in dimensions higher than 3?

Same argument. The dual of a deformed product polytope in dimension d
intersects some 2-plane in a polygon with O(n^floor(d/2))
faces. Again, project to dimension d-1 along a line parallel to the
2-plane. 

- What if the triangulation is Delaunay?

Beats me. I tried a little to munge the deformed products construction
so that the vertices all lay on a paraboloid, but no luck. We showed
(same paper) that a slice through a *cyclic* 4-polytope can only have
a linear number of faces, so it's possible that the same is true of
the CH of points on a paraboloid.

The reference is:

Nina Amenta and G"unter Ziegler.
Deformed products and maximal shadows of polytopes, 
in: Advances in Discrete and Computational Geometry
(B. Chazelle, J.E. Goodman, R. Pollack, eds.), Contemporary
Mathematics 223 (1999), Amer. Math. Soc., Providence, 57-90.
ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Report-502-1996.ps.Z

Conference version:

Nina Amenta and G"unter Ziegler.
Shadows and slices of polytopes,
Proceedings of the 12th Annual ACM Symposium on Computational
Geometry, pages 10-19, (1996).
http://www.cs.utexas.edu/users/amenta/pubs/projection.ps.gz


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme