Stabbing pairwise disjoint translates in linear time
Peter Egyed, Rephael Wenger · 1989
In general, finding a line stabber for a family of n objects in the plane takes ω(n log n) time. However, we show how to find a line stabber for a family of n pairwise disjoint convex translates in the plane in linear time. Our algorithm still runs in optimal Ο (n log n) time when the translates are not pairwise disjoint.