The field of computational geometry is concerned with the analysis of geometric algorithms. For such algorithms, correctness and efficiency proofs are constructed, or problems are proven to be hard when no correct and efficient algorithm exists. In order to be able to do this, several assumptions about the input data for geometric algorithms are made. One of them is that this data is correct, with absolute certainty and infinite precision. In practical applications, this is often not the case, and as a result the value of these theoretical guarantees may be questionable.

If we want to supply geometric algorithms with theoretical guarantees that are actually observed in practice, we have to loosen our assumptions about the input data to a more realistic level. Depending on the application, we may be confident that each data point, for example, is not more than some value epsilon away from its given position. We can then construct algorithms that are guaranteed to be correct and efficient as long as the input satisfies this weaker assumption. Furthermore, we can analyse how the imprecision in the input influences the accuracy of the output.

In this talk, I will give an overview of how data imprecision can be modelled in computational geometry, and which types of questions can be or have been asked about imprecise data.