Fast and Accurate Intersections on a Sphere
- 10 April 2026
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 48 (2) , B208-B232
Abstract
We introduce a fast, high-precision algorithm for calculating intersections between great circle arcs and lines of constant latitude on the unit sphere. We first propose a simplified intersection point formula with improved speed and numerical robustness over the ones traditionally implemented in geoscience software. We then show how algorithms based on the concept of error-free transformations (EFT) can be applied to evaluate this formula within a relative error bound that is on the order of machine precision. We demonstrate that, with a vectorized and parallelized implementation, this enhanced accuracy is achieved with no compute time overhead compared to a direct calculation in hardware floating point, making our algorithm suitable for performance-sensitive applications like regridding of high-resolution climate data. In contrast, evaluating our formula using high-precision data types like quadruple precision and arbitrary precision, or using the robust intersection computation routines from the Computational Geometry Algorithms Library, leads to significant computational overhead, especially since these alternatives inhibit vectorization. More generally, our work demonstrates how EFT techniques can be combined and extended to implement nontrivial geometric calculations with high accuracy and speed. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SISC and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/hongyuchen1030/accurate-operator-reproducibility/tree/main and in the supplementary materials ( M173761_Supplementary_Materials_1.pdf [265KB], accurate-operator-reproducibility-main.zip [199KB]). [Formula: see text]Keywords
All Related Versions
Funding Information
- U.S. Department of Energy
- PCMDI
- Lawrence Livermore National Laboratory (DE-AC52-07NA27344)
This publication has 26 references indexed in Scilit:
- Fast and accurate computation of the Euclidean norm of a vectorJapan Journal of Industrial and Applied Mathematics, 2023
- Handbook of Floating-Point Arithmetic2018
- Further analysis of Kahan’s algorithm for the accurate computation of $2\times 2$ determinantsMathematics of Computation, 2013
- Arrangements on Parametric Surfaces II: Concretizations and ApplicationsMathematics in Computer Science, 2010
- Conservative interpolation between unstructured meshes via supermesh constructionComputer Methods in Applied Mechanics and Engineering, 2009
- IEEE Standard for Binary Floating-Point Arithmetic2008
- Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric PredicatesDiscrete & Computational Geometry, 1997
- Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator1996
- Inaccuracy in quasi-Newton methods: Local improvement theorems1984
- A floating-point technique for extending the available precisionNumerische Mathematik, 1971