Skip to main content
U.S. flag

An official website of the United States government

Dot Gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.


The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

An Efficient Search Algorithm For Minimum Covering Polygons On The Sphere


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.

Article / Publication Data
Available Metadata
Accepted On
March 11, 2013
Fiscal Year
Publication Name
Siam J. Sci. Comput.
Published On
June 01, 2013
Final Online Publication On
June 01, 2013
Print Volume
Print Number
Page Range
Submitted On
June 11, 2012


Not available


Authors who have authored or contributed to this publication.

Not available