An improved method of analysis of coverage of areas of the Earth by a constellation of radio-communication or scientific-observation satellites has been developed. This method is intended to supplant an older method in which the global-coverage- analysis problem is solved from a ground-to-satellite perspective. The older method is suitable for coarse-grained analysis of coverage of a constellation of a few satellites, but the algorithms of the older method are too slow and cumbersome for the large scope of the problem of analysis of coverage of a modern constellation of many satellites intended to provide global coverage all the time. In contrast, the present method provides for rapid and efficient analysis. This method is derived from a satellite-to-ground perspective and involves a unique combination of two techniques for multiresolution representation of map features on the surface of a sphere.

Using a Multiresolution Map to analyze a circular region, it is not necessary to resort to full resolution everywhere. Large areas with the same value can be represented by a few large squares; smaller squares are needed only to resolve details of the boundary.
The first of the two techniques, called "visual calculus," is one that embodies the satellite-to-ground perspective and assists in the visualization of global coverage. In visual calculus, a satellite can be regarded as "painting" its field of view or other coverage field onto the ground to generate simple maps. These maps are two-dimensional projections of the globe, with ground tracks and station masks for each satellite in a constellation. These maps are processed further to generate composite maps that answer a variety of simple and complex questions regarding coverage, both for specific ground points and for regions.

For the purpose of computational implementation, a map is represented by an integer function of latitude and longitude, analogous to the more familiar map color as a function of latitude and longitude. More specifically, a map object M is defined by M(l,λ):(l,λ)→i, where l is latitude, λ is longitude, and i is the integer value at the point in question. The processing of maps to generate composite maps and answer questions about coverage involves, among other things, the use of an algebra in which map objects are manipulated by unary, binary, Boolean, and other operators. Examples of operators include one that finds the distance from a given point to a map boundary and one that finds what percentage of a map has a given integer value.

The second technique essential to the present method is the use of a quad-tree data structure in implementing the visual calculus. For this purpose, the map function is redefined to provide not only the integer value for a given location but also information on how far one must travel from that location to encounter a change in the map. A point quad tree is well suited to a multiresolution representation of map features on the surface of a sphere.

In essence, a quad tree is a data-compression construct that takes advantage of the facts that (1) a typical map contains only a few regions with a few values and (2) at each point, most values in the neighborhood are the same value. In a quad tree, squares of pixels that have the same value are represented as one large square. It does not become necessary to do calculations on a subdivision of a square until a map boundary subdivides the square. Thus, it is not necessary to fix resolution at the beginning of an analysis. If higher resolution is needed for a particular map, it can be achieved through finer subdivisions.

The main reason for choosing a quad-tree data structure instead of a pixel-based data structure is that the point-quad-tree structure requires less data-storage space. This computational advantage arises because the number of subdivisions needed in a given case is approximately proportional to the length of the boundary between regions, instead of proportional to the area of the regions as in a pixel representation. It is necessary to subdivide only those squares that straddle a boundary (see figure), and because a boundary is one-dimensional, the number of subdivisions for the required resolution scales linearly, rather than quadratically as when subdividing an area with pixels.

This work was done by Martin W. Lo, George Hockney, and Bruce Kwan of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category. NPO-20557.