Stabbing numbers of triangulations

Jonathan Shewchuk jrs at CS.Berkeley.EDU
Mon Mar 1 15:59:57 PST 1999

It is well known that a tetrahedralization of n vertices in E^3 may have
Theta(n^2) tetrahedra.

My main question:

- 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

If anyone knows an answer to this, I would be very grateful to hear it.

Some additional questions:

- How about in dimensions higher than 3?
- What if the triangulation is Delaunay?

Jonathan Shewchuk
Computer Science Division
University of California at Berkeley
jrs at

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme

More information about the Compgeom-announce mailing list