A framework for robust realistic geometric computations

With Ivor van der Hoog and Tillmann Miltzow.

Preprint, December 2019.

We propose a new paradigm for robust geometric computations that complements the classical fixed precision paradigm (interval geometry, ε-geometry and, stable algorithms) and the exact geometric computation paradigm. We provide a framework where we study algorithmic problems under smoothed analysis of the input, the relaxation of the problem requirements, or the witness of a recognition problem. Our framework specifies a widely applicable set of prerequisites that make real RAM algorithms suitable for smoothed analysis. We prove that suitable algorithms can (under smoothed analysis) be robustly executed with expected logarithmic bit-precision. This shows in a formal way that inputs which need high bit-precision are contrived and that these algorithms are likely robust for realistic input. Interestingly, our techniques generalize to recognition problems (recognition of realizable order types or disk intersection graphs) and problems with a natural notion of resource augmentation (geometric packing, the art gallery problem).

Our results have practical implications for many geometric algorithms: If their input is slightly perturbed before execution then the expected bit-precision for robust computation is logarithmic. Our results also have theoretical implications for some ∃R-hard problems: we show that many real verification algorithms under slight perturbations of their witness require expected logarithmic bit-precision. These problems have input instances where their real verification algorithm requires at least exponential bit-precision, which makes it difficult to place these ∃R-hard problems in NP. Our results imply for a host of ∃R-complete problems that this exponential bit-precision phenomenon comes from nearly degenerate instances.

It is not evident that problems that have a real verification algorithm belong to ∃R. Therefore, we conclude with a real RAM analogue to the Cook-Levin Theorem, which shows that algorithmic problems belong to ∃R, if and only if there is a real verification algorithm. This gives an easy proof of ∃R-membership, as real verification algorithms are much more versatile than ETR-formulas.

Publications - Jeff Erickson (jeffe@illinois.edu) 05 Dec 2019