(LaTeX) Abstract: |
Controlled Perturbation (CP, for short) is an approach to implement
efcient and robust geometric algorithms using the computational speed of builtin
nite precision arithmetic, while bypassing precision problems during the computation.
Furthermore it avoids the time-consuming and error-prone discussion
of degenerate cases. CP replaces the input objects by a set of randomly perturbed
(moved, scaled, stretched, etc.) objects such that the algorithm is guaranteed to
compute the exact combinatorial structure that these objects imply.
This paper is meant as a guide how to decide if CP can be applied to a given
algorithm, and if, how to correlate all CP parameters: the perturbation amount d ,
the arithmetic precision $L$, the maximum range of input values $[−m,m]$, the number
of input objects $n$, the error bound $\mathcal{B}_f$ of the (chosen) predicate evaluations,
and the probability $\mathcal{P}$ of a successful computation. For this purpose we present
a general methodology to analyze predicate functions that leads to an inequality
correlating these parameters and hence to bounds on the precision or perturbation
amount. In particular we treat the case of the wide used class of polynomial predicates
in detail. Advantages, drawbacks and implementation issues are discussed. |
Edit History (please click the blue arrow to see the details)