We present a systematic study of the expected complexity of the intersection of geometric objects. We first study the expected size of the intersection between a random Voronoi diagram and a generic geometric object that consists of a finite collection of line segments in the plane. Using this result, we explore the intersection complexity of a random Voronoi diagram with the following target objects which may or may not be random: a line segment, a Voronoi diagram, a minimum spanning tree, a Gabriel graph, a relative neighborhood graph, a Hamiltonian circuit, a furthest point Voronoi diagram, a convex hull, a k-dimensional tree, and a rectangular grid.

Additional Metadata
Keywords Computational geometry, Intersection complexity, Probabilistic analysis, Range searching
Persistent URL dx.doi.org/10.1016/S0925-7721(98)00004-2
Journal Computational Geometry
Bose, P, & Devroye, L. (Luc). (1998). Intersections with random geometric objects. Computational Geometry, 10(3), 139–154. doi:10.1016/S0925-7721(98)00004-2