{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T08:09:37Z","timestamp":1774339777977,"version":"3.50.1"},"reference-count":48,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T00:00:00Z","timestamp":1773792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004489","name":"Mitacs","doi-asserted-by":"publisher","award":["IT39793"],"award-info":[{"award-number":["IT39793"]}],"id":[{"id":"10.13039\/501100004489","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.3390\/ijgi15030135","type":"journal-article","created":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T14:14:05Z","timestamp":1773843245000},"page":"135","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Spherical Geodesic Bounds and a k-Circle Coverage Formulation"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-9820-5770","authenticated-orcid":false,"given":"Josiah","family":"Lansang","sequence":"first","affiliation":[{"name":"Department of Computer Science, Faculty of Science, University of Calgary, Calgary, AB T2N 1N4, Canada"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9440-7562","authenticated-orcid":false,"given":"Faramarz","family":"F. Samavati","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Faculty of Science, University of Calgary, Calgary, AB T2N 1N4, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2026,3,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Ericson, C. (2004). Real-Time Collision Detection, CRC Press.","DOI":"10.1201\/b14581"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Gottschalk, S., Lin, M.C., and Manocha, D. (1996). OBB-Tree: A Hierarchical Structure for Rapid Interference Detection. Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, Association for Computing Machinery. SIGGRAPH \u201996.","DOI":"10.1145\/237170.237244"},{"key":"ref_3","unstructured":"Pharr, M., Jakob, W., and Humphreys, G. (2016). Physically Based Rendering: From Theory to Implementation, Morgan Kaufmann. [3rd ed.]."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/2945.675649","article-title":"Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs","volume":"4","author":"Klosowski","year":"1998","journal-title":"IEEE Trans. Vis. Comput. Graph."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"van den Bergen, G. (2003). Collision Detection in Interactive 3D Environments, Morgan Kaufmann.","DOI":"10.1201\/9781482297997"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, Springer. [3rd ed.].","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Snyder, J.P. (1987). Map Projections: A Working Manual, U.S. Geological Survey Professional Paper 1395.","DOI":"10.3133\/pp1395"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"10","DOI":"10.3138\/27H7-8K88-4882-1752","article-title":"An equal-area map projection for polyhedral globes","volume":"29","author":"Snyder","year":"1992","journal-title":"Cartographica"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Alderson, T., Purss, M., Du, X., Mahdavi-Amiri, A., and Samavati, F. (2019). Digital Earth Platforms. Manual of Digital Earth, Springer.","DOI":"10.1007\/978-981-32-9915-3_2"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Harrison, E., Mahdavi-Amiri, A., and Samavati, F. (2011, January 4\u20136). Optimization of Inverse Snyder Polyhedral Projection. Proceedings of the 2011 International Conference on Cyberworlds, Banff, AB, Canada.","DOI":"10.1109\/CW.2011.36"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.cag.2015.08.005","article-title":"A survey of Digital Earth","volume":"53","author":"Alderson","year":"2015","journal-title":"Comput. Graph."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1016\/j.ejor.2008.03.046","article-title":"The variable radius covering problem","volume":"196","author":"Berman","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1515\/comp-2020-0219","article-title":"Optimization of a k-covering of a bounded set with circles of two given radii","volume":"11","author":"Khorkov","year":"2021","journal-title":"Open Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s10589-008-9191-8","article-title":"Covering a compact polygonal set by identical circles","volume":"46","author":"Stoyan","year":"2010","journal-title":"Comput. Optim. Appl."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.gmod.2016.05.002","article-title":"Multiresolution on spherical curves","volume":"86","author":"Alderson","year":"2016","journal-title":"Graph. Model."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Thorpe, J.A. (1979). The Exponential Map. Elementary Topics in Differential Geometry, Springer. Undergraduate Texts in Mathematics.","DOI":"10.1007\/978-1-4612-6153-7"},{"key":"ref_17","unstructured":"do Carmo, M.P. (1976). Differential Geometry of Curves and Surfaces, Prentice-Hall, Inc."},{"key":"ref_18","unstructured":"OpenStreetMap Contributors (2024, November 13). Bounding Box\u2014OpenStreetMap Wiki. Available online: https:\/\/wiki.openstreetmap.org\/wiki\/Bounding_Box."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Welzl, E. (1991). Smallest enclosing disks (balls and ellipsoids). New Results and New Trends in Computer Science, Springer.","DOI":"10.1007\/BFb0038202"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1145\/361002.361007","article-title":"Multidimensional Binary Search Trees Used for Associative Searching","volume":"18","author":"Bentley","year":"1975","journal-title":"Commun. ACM"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Liu, S.W., Fischer, M., Yoo, P.D., and Ritschel, T. (2024). Neural Bounding. arXiv.","DOI":"10.1145\/3641519.3657442"},{"key":"ref_22","unstructured":"Sharp, N., and Jacobson, A. (2022). Geometry Processing with Neural Implicit Surfaces. Proceedings of the ACM SIGGRAPH 2022 Conference Proceedings, ACM."},{"key":"ref_23","unstructured":"Fujieda, S., Kao, C.C., and Harada, T. (2023). Neural Intersection Function. arXiv."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3728295","article-title":"LSNIF: Locally-Subdivided Neural Intersection Function","volume":"8","author":"Fujieda","year":"2025","journal-title":"Proc. Acm Comput. Graph. Interact. Tech."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Zhang, Q., Hou, J., Adikusuma, Y.Y., Wang, W., and He, Y. (2023, January 10\u201316). NeuroGF: A Neural Representation for Fast Geodesic Distance and Path Queries. Proceedings of the Advances in Neural Information Processing Systems (NeurIPS), New Orleans, LA, USA.","DOI":"10.52202\/075280-0855"},{"key":"ref_26","unstructured":"Huberman, D., and Kimmel, R. (2023, January 1\u20135). Deep Geodesic Solver: Learning High-Order Geodesics on Surfaces. Proceedings of the International Conference on Learning Representations (ICLR), Kigali, Rwanda."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/971697.602266","article-title":"R-trees: A dynamic index structure for spatial searching","volume":"14","author":"Guttman","year":"1984","journal-title":"ACM SIGMOD Rec."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H.P., Schneider, R., and Seeger, B. (1990, January 23\u201326). The R*-tree: An efficient and robust access method for points and rectangles. Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, USA.","DOI":"10.1145\/93597.98741"},{"key":"ref_29","first-page":"500","article-title":"Hilbert R-tree: An improved R-tree using fractals","volume":"Volume 94","author":"Kamel","year":"1994","journal-title":"Proceedings of the VLDB"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Katayama, N., and Satoh, S. (1997). The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. Proceedings of the ACM SIGMOD International Conference on Management of Data, ACM.","DOI":"10.1145\/253260.253347"},{"key":"ref_31","unstructured":"Google (2025, April 04). S2 Geometry Library Documentation. Available online: https:\/\/s2geometry.io\/."},{"key":"ref_32","unstructured":"Uber Engineering (2025, April 04). H3: Uber\u2019s Hexagonal Hierarchical Spatial Index. Global. Available online: https:\/\/www.uber.com\/en-RO\/blog\/h3\/."},{"key":"ref_33","first-page":"20","article-title":"Proofs of the Fundamental Theorems of Spherical Trigonometry","volume":"32","author":"Clark","year":"1930","journal-title":"Trans. Am. Math. Soc."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1111\/j.1538-4632.1976.tb00529.x","article-title":"Applications of the location set covering problem","volume":"8","author":"ReVelle","year":"1976","journal-title":"Geogr. Anal."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1111\/j.1435-5597.1974.tb00902.x","article-title":"The maximal covering location problem","volume":"32","author":"Church","year":"1974","journal-title":"Pap. Reg. Sci. Assoc."},{"key":"ref_36","first-page":"25","article-title":"A review of covering problems in facility location","volume":"1","author":"Schilling","year":"1993","journal-title":"Locat. Sci."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Daskin, M.S. (1995). Network and Discrete Location: Models, Algorithms, and Applications, John Wiley & Sons.","DOI":"10.1002\/9781118032343"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF02564786","article-title":"Polynomial algorithms for parametric min-quantile and maxcovering planar location problems with locational constraints","volume":"6","author":"Carrizosa","year":"1998","journal-title":"Top"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/S0377-2217(98)00335-X","article-title":"Undesirable facility location in the plane with minimal covering objectives","volume":"119","author":"Plastria","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0969-6989(98)80009-X","article-title":"Location of multiple retail facilities with a limited budget","volume":"5","author":"Drezner","year":"1998","journal-title":"J. Retail. Consum. Serv."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s10107-003-0468-5","article-title":"Optimal location and design of a competitive facility","volume":"100","author":"Plastria","year":"2004","journal-title":"Math. Program."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"1274","DOI":"10.1016\/j.ejor.2006.02.005","article-title":"Solving a Huff-like competitive location and design model for profit maximization in the plane","volume":"179","author":"Pelegrin","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/j.ejor.2006.07.021","article-title":"Competitive facility location and design problem","volume":"182","author":"Aboolian","year":"2008","journal-title":"Eur. J. Oper. Res."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Mirzai Golpayegani, A., Hasan, M., and Samavati, F.F. (2025). Real-Time Multiresolution Management of Spatiotemporal Earth Observation Data Using DGGS. Remote Sens., 17.","DOI":"10.3390\/rs17040570"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Wecker, L., Hall, J., and Samavati, F. (2024). Constructing Efficient Mesh-Based Global Grid Systems with Reduced Distortions. ISPRS Int. J. Geo-Inf., 13.","DOI":"10.3390\/ijgi13110373"},{"key":"ref_46","unstructured":"Goodchild, M.F. (2000, January 26\u201328). Discrete global grids for digital Earth. Proceedings of the 1st International Conference on Discrete Global Grids, Santa Barbara, CA, USA."},{"key":"ref_47","unstructured":"Makhorin, A. (2013). GNU Linear Programming Kit (GLPK) Reference Manual; Section on glp_intopt: MIP solver based on the branch-and-cut method, Free Software Foundation (FSF)."},{"key":"ref_48","unstructured":"Hughes, J.F., van Dam, A., McGuire, M., Sklar, D.F., Foley, J.D., Feiner, S.K., and Akeley, K. (2014). Computer Graphics: Principles and Practice, Addison-Wesley Professional. [3rd ed.]."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/15\/3\/135\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T05:12:21Z","timestamp":1774329141000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/15\/3\/135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,18]]},"references-count":48,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2026,3]]}},"alternative-id":["ijgi15030135"],"URL":"https:\/\/doi.org\/10.3390\/ijgi15030135","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,18]]}}}