| Month: 12 (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Project co-funded by the European Commission within FP6 (2002–2006) under contract nr. IST-006413 Most geometric algorithms are idealistic in the sense that they are designed for the Real-RAM model of computation and for inputs in general position. Real inputs may be degenerate and floating point arithmetic is only an approximation of real arithmetic. Perturbation replaces an input by a nearby input which is (hopefully) in general position and on which the algorithm can be run with floating point arithmetic. Controlled perturbation as proposed by Halperin et al. calls for more: control over the amount of perturbation needed for a given precision of the floating point system. Or conversely, a control over the precision needed for a given amount of perturbation. Halperin et al. gave controlled perturbation schemes for arrangements of polyhedral surfaces, spheres, and circles. We extend their work and point out that controlled perturbation is a general scheme for converting idealistic algorithms into algorithms which can be executed with | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||