Bibliographic Details
| Title: |
Fast and Accurate Intersections on a Sphere. |
| Authors: |
Chen, Hongyu1 (AUTHOR) hyvchen@ucdavis.edu, Ullrich, Paul A.2 (AUTHOR) paullrich@ucdavis.edu, Panetta, Julian3 (AUTHOR) jpanetta@ucdavis.edu |
| Source: |
SIAM Journal on Scientific Computing. 2026, Vol. 48 Issue 2, pB208-B232. 25p. |
| Subjects: |
Spherical geometry, Algorithms, Geospatial data, Geodesics, Parallel programming, Numerical analysis |
| 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 and in the supplementary materials ( [265KB], [199KB]). [ABSTRACT FROM AUTHOR] |
|
Copyright of SIAM Journal on Scientific Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
