A GENERAL-APPROACH TO REMOVING DEGENERACIES

We wish to increase the power of an arbitrary algorithm designed for n ondegenerate input by allowing it to execute on all inputs. We concent rate on infinitesimal symbolic perturbations that do nor affect the ou tput for inputs in general position. Otherwise, if the problem mapping is continuous, the input and output space topology are at least as co arse as the real euclidean one, and the output space is connected, the n our perturbations make the algorithm produce an output arbitrarily c lose or identical to the correct one, For a special class of algorithm s, which includes several important algorithms in computational geomet ry, we describe a deterministic method that requires no symbolic compu tation. Ignoring polylogarithmic factors, this method increases the wo rst-case bit complexity only by a multiplicative factor which is linea r in the dimension of the geometric space. For general algorithms, a r andomized scheme with an arbitrarily high probability of success is pr oposed: the bit complexity is then bounded by a small-degree polynomia l in the original worst-case complexity. In addition to brine simpler than previous ones, these are the first efficient perturbation methods .