To quote David Eppstein: ``A major bottleneck in proving NP-completeness for geometric problems is a mismatch between the real-number and Turing machine models of computation: one is good for geometric algorithms but bad for reductions, and the other vice versa. Specifically, it is not known on Turing machines how to quickly compare a sum of distances (square roots of integers) with an integer or other similar sums, so even (decision versions of) easy problems such as the minimum spanning tree are not known to be in NP.''
John A. Anderson (firstname.lastname@example.org) has an unpublished proof (Aug 2003) of a similar bound:
At the other extreme, Qian and Wang [QW04,QW05] show an upper bound on r(n, k) of O(n-2k+). This upper bound on r(n, k) implies a lower bound on lg 1/r(n, k), that is, on how many bits we need to compute from the square roots to determine the sign of the difference. In particular, it settles (positively) a question posed here by Erik Demaine (Nov. 2001): can the number of bits required to distinguish the difference from zero ever exceed the total number of bits in the input integers?
A slight variation on the problem is to ask (e.g., for k = 2), how close can + be to an integer; Dana Angluin and Sarah Eisenstat [AE04] proved a bound of Θ(1/n3/2) on this integrality gap.
Also, [Blö91] may be relevant.