Abstract
We define a new abstract framework for optimization problems, violator spaces, which is a proper generalization of the LP-type problems introduced by Sharir and Welzl. We show that Clarkson's randomized algorithm for low-dimensional linear programming works in the context of violator spaces.
For example, in this way we obtain the fastest known algorithm for the P-matrix generalized linear complementarity problem with a constant number of blocks. We also give two new characterizations of LP-type problems.