A GENERAL-APPROACH TO REMOVING DEGENERACIES

We wish to increase the power of an arbitrary algorithm designed for nondegenerate input by allowing it to execute on all inputs. We concentrate on infinitesimal symbolic perturbations that do nor affect the output for inputs in general position. Otherwise, if the problem mapping is continuous, the input and output space topology are at least as coarse as the real euclidean one, and the output space is connected, then our perturbations make the algorithm produce an output arbitrarily close or identical to the correct one, For a special class of algorithms, which includes several important algorithms in computational geometry, we describe a deterministic method that requires no symbolic computation. Ignoring polylogarithmic factors, this method increases the worst-case bit complexity only by a multiplicative factor which is linear in the dimension of the geometric space. For general algorithms, a randomized scheme with an arbitrarily high probability of success is proposed: the bit complexity is then bounded by a small-degree polynomial in the original worst-case complexity. In addition to brine simpler than previous ones, these are the first efficient perturbation methods.