How to Cover Most of a Point Set with a V-Shape of Minimum Width

A V-shape is an infinite polygonal region bounded by two pairs of parallel rays emanating from two vertices (see Figure 1). We describe a randomized algorithm that, given n points and an integer k ≥ 0, finds the minimum-width V-shape enclosing all but k of the points with probability 1 − 1/nc for any c> 0, with expected running time O(cn2(k + 1)4 log n(log n log log n + k)).