Spherical Geodesic Bounds and a k-Circle Coverage Formulation

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

Bounding overwatch · Geodesic · Geodesic map · Minimum bounding box · Polytope · Solving the geodesic equations · Torus · Computational Geometry and Mesh Generation · Data Management and Algorithms · Geographic Information Systems Studies

• Constructing Efficient Mesh-Based Global Grid Systems with Reduced Distortions

  Open Access•Lakin Wecker, John Hall et al.•ISPRS International Journal of…•2024

  Add to list

• The Maximal Covering Location Problem

  Open Access•Richard L Church, CHARLES R VELLE•Papers of the Regional Science…•1974

  Add to list