Spherical Geodesic Bounds and a k-Circle Coverage Formulation

Abstract

In this article, we introduce analogues of classic Euclidean bounds, including spherical caps, geodesic axis-aligned bounding boxes (AABBs), geodesic oriented bounding boxes (OBBs), and geodesic k-discrete oriented polytopes (k-DOPs). We also formulate k-circle coverage, a union of variable-radius caps solved by a binary integer program over candidates generated from Discrete Global Grid System (DGGS)-based rasterization. As all constructions run directly on the spherical surface, S2, they preserve geodesic distances and avoid projection distortion. We benchmark these methods on seven country boundary polygons consisting of thousands of points, and report construction time, memory, tightness, and query throughput. Results show our analytic geodesic bounds deliver orders of magnitude improvements over exact tests, with trade-offs in tightness: spherical caps are fastest but loosest; geodesic OBBs are a strong balance; geodesic k-DOPs consistently have the tightest bounds. k-circle coverage has spherical cap query speed while also having locally adaptive fits; construction time increases with DGGS resolution. Altogether, these bounds specific to the sphere provide practical, conservative filters for globe-scale Digital Earth queries.