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.

, , ,
doi.org/10.1016/S0925-7721(98)00004-2
Computational Geometry
School of Computer Science

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