On geometric optimization with few violated constraints

We investigate the problem of finding the best solution satisfying all butk of the given constraints, for an abstract class of optimization problems introduced by Sharir and Welzl—the so-calledLP-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 butk of the givenn points in the plane, we obtain anO(n logn+k ³ n ^ε) algorithm; this improves previous results fork small compared withn but moderately growing. We also establish some results concerning general properties ofLP-type problems. This research was supported in part by Charles University Grant No. 351 and Czech Republic Grant GAČR 201/93/2167. Part of this research was performed while the author was visting the Computer Science Institute, Free University Berlin, and it was supported by the German-Israeli Foundation of Scientific Research and Development (G.I.F.), and part while visiting the Max-Planck Institute for Computer Science in Saarbrücken.