On the stabbing number of a random Delaunay triangulation

摘要

We consider a Delaunay triangulation defined on n points distributed independently and uniformly on a planar compact convex set of positive volume. Let the stabbing number be the maximal number of intersections between a line and edges of the triangulation. We show that the stabbing number S-n is Theta(root n) in the mean, and provide tail bounds for P{S-n >= t root n}. Applications to planar point location, nearest neighbor searching, range queries, planar separator determination, approximate shortest paths, and the diameter of the Delaunay triangulation are discussed. (c) 2006 Elsevier B.V. All rights reserved.