Given once, 2013
Hitting and Piercing Rectangles Induced by a Point Set
Some point pierces n²/8 of the rectangles spanned by n points, and that is tight
An intermediate research talk, for graduate students and up.
Abstract
Draft, not yet checked by meAny n points in the plane induce axis-parallel rectangles, one for each pair of points. Does some point pierce many of these rectangles, and how few points are needed to hit all of them?
On piercing, some point lies in at least n²/8 of the induced rectangles, and this is tight; if the point must come from the input, the tight bound is n²/16. For a large enough subfamily of m rectangles, some point lies in at least m³/(24n⁴) of them. On hitting, I find minimum hitting sets for induced skyline rectangles in O(n log n) time, give exact bounds for skylines and slabs, and show NP-completeness for induced lines.
The slides
The viewer needs JavaScript; the PDF below works without it.