An Efficient Search Algorithm For Minimum Covering Polygons On The Sphere

Abstract

One of the computationally intensive tasks in the numerical simulation of dynamic systems discretized on an unstructured grid over the sphere is to find a number of spherical minimum covering polygons of given locations, whose vertices are chosen from the grid points. Algorithms have been proposed attempting to perform this task efficiently. However, these algorithms only reduce the linear search time for each polygon vertex candidate by a constant factor, and their polygon search algorithms are mostly heuristic and tailored for specific classes of grids. With the increase in grid resolution, the number of unstructured grid types, and dynamic generation of variable resolution grids, these algorithms are no longer suitable for the computational task. It is necessary to develop a more general, efficient, and robust search algorithm. We propose an algorithm, built on a modified kd-tree algorithm, to search for minimum covering polygons of given locations from a set of grid points on the sphere. After an $O(nlog{n})$ time initialization to construct the kd-tree from $n$ grid points, the proposed algorithm takes an $O(log{n})$ expected time to find the minimum covering polygon for a given location on the sphere (or the same expected asymptotic time with a smaller constant to obtain an approximate solution). We present the modified kd-tree algorithm, showing its applicability to the search problem. We present the search algorithm for the spherical minimum covering polygon and an analysis of the algorithm's computational complexity. To demonstrate the computational efficiency of the proposed search algorithm, we apply it to the data sets of randomly generated data points on the sphere from various distributions and to the data sets of two types of spherical grids, icosahedral grid and Gaussian grid, which are widely used in the numerical simulation on spherical bodies.