On geometric optimization with few violated constraints
Jiřı́ Matoušek · 1994
We investigate the problem of finding the best solution satisfying all but k of the given constraints, for an abstract class of optimization problems introduced by Sharir and Welzl—the so-called LP-type problems. We give a general algorithm and discuss its efficient implementations for specific geometric problems. For instance, for the problem of computing the smallest circle enclosing all but k of the given n points in the plane, we obtain an O(nlogn+k3nε) algorithm; this improves previous results for k small compared ton but moderately growing.