transitive floating point comparison with (absolute) tolerance

Question

I want to compare two floating point numbers for equality relative to a known absolute tolerance. However, this is inside an algorithm I wrote quite some time ago, and I believe the logic of that algorithm would get corrupted if the equality relation is not transitive.

Some false negatives are no problem, i.e. if two "equal" numbers compare unequal, all that will happen is that the algorithm will use a bit more time and memory. However, I now got input data preprocessed by another algorithm (to smooth out corners), but that algorithm added noise to every single straight line, which leads to memory consumption issues (> 4GB) during my algorithm.

I see essentially two options, how I could fix the issue:

• I could try to remove the "noise" from the results of the preprocessing algorithm.
• I could try to find a way to do tolerance based equality comparison in a transitive way.

The first approach looks easier to me. I would basically have a fixed set of doubles and would need to pick a set of representatives such that every double in the set is within epsilon of a representative. The only idea I have for the second approach is to snap the values to a grid for the comparison. However, I vaguely remember having implemented such a grid snapping approach before, but it broke down as soon as the (c++) compiler started to inline the corresponding code. I fixed this by moving the snapping code to a different translation unit, but later rewrote the code to make the snapping obsolete.

Question

1. Is it possible to do tolerance based equality comparisons (in c++) without violating transitivity?

2. What is a good way to implement a "noise removal" algorithm? My approach would probably be to keep a sorted list of representatives, and look up each new double value by bisection in that list, leading to a $O(n \log n)$ runtime and $O(n)$ (additional) memory consumption for the "noise removal" algorithm.

Answer 1

If you have all the numbers up front, you can efficiently compute the transitive closure of tolerance-based comparison with a union-find structure. First loop through all pairs of nearby points (e.g., using a bounding box hierarchy), and for each pair within your tolerance mark them as merged in the union-find. Later on, compare points for equality by checking if they're in the same union-find component.

Answer 2

You can't do equality comparison transitively with a tolerance. In the past I've used methods that snap points onto a grid by casting a double to a float and back to double. This is not failsafe, but it often gets rid of some of the more annoying cases.