2017/07/26 by Daniel Bahrdt, Bahrdt, Daniel, Martin P. Seybold +1
Computer Science · Engineering · #Computational Geometry and Mesh Generation #Advanced Numerical Analysis Techniques #Digital Image Processing Techniques
paper · pdf · doi:10.48550/arxiv.1707.08549
Each non-zero point in ℝd identifies a closest point x on the unit sphere \mathbbSd-1. We are interested in computing an ε-approximation y ∈ ℚd for x, that is exactly on \mathbbSd-1 and has low bit size. We revise lower bounds on rational approximations and provide explicit, spherical instances. We prove that floating-point numbers can only provide trivial solutions to the sphere equation in ℝ2 and ℝ3. Moreover, we show how to construct a rational point with denominators of at most 10(d-1)/ε2 for any given ε∈ (0,\tfrac 1 8], improving on a previous result. The method further benefits from algorithms for simultaneous Diophantine approximation. Our open-source implementation and experiments demonstrate the practicality of our approach in the context of massive data sets Geo-referenced by latitude and longitude values.