A General Approach to Removing Degeneracies

Publisher Website
Google Scholar
Abstract
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 not 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 only the worst-case bit complexity by a multiplicative factor which is linear in the dimension of the geometric space. For general algorithms, a randomized scheme with 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 being simpler than previous ones, these are the first efficient perturbation methods.

This publication has 15 references indexed in Scilit: