Fast and Accurate Intersections on a Sphere.
Saved in:
| 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 |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 195221957 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Fast and Accurate Intersections on a Sphere. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Chen%2C+Hongyu%22">Chen, Hongyu</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> hyvchen@ucdavis.edu</i><br /><searchLink fieldCode="AR" term="%22Ullrich%2C+Paul+A%2E%22">Ullrich, Paul A.</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> paullrich@ucdavis.edu</i><br /><searchLink fieldCode="AR" term="%22Panetta%2C+Julian%22">Panetta, Julian</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> jpanetta@ucdavis.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Scientific+Computing%22">SIAM Journal on Scientific Computing</searchLink>. 2026, Vol. 48 Issue 2, pB208-B232. 25p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Spherical+geometry%22">Spherical geometry</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Geospatial+data%22">Geospatial data</searchLink><br /><searchLink fieldCode="DE" term="%22Geodesics%22">Geodesics</searchLink><br /><searchLink fieldCode="DE" term="%22Parallel+programming%22">Parallel programming</searchLink><br /><searchLink fieldCode="DE" term="%22Numerical+analysis%22">Numerical analysis</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=195221957 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/25M1737614 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 25 StartPage: B208 Subjects: – SubjectFull: Spherical geometry Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Geospatial data Type: general – SubjectFull: Geodesics Type: general – SubjectFull: Parallel programming Type: general – SubjectFull: Numerical analysis Type: general Titles: – TitleFull: Fast and Accurate Intersections on a Sphere. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Chen, Hongyu – PersonEntity: Name: NameFull: Ullrich, Paul A. – PersonEntity: Name: NameFull: Panetta, Julian IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 03 Text: 2026 Type: published Y: 2026 Identifiers: – Type: issn-print Value: 10648275 Numbering: – Type: volume Value: 48 – Type: issue Value: 2 Titles: – TitleFull: SIAM Journal on Scientific Computing Type: main |
| ResultId | 1 |
