A 2003 article written by George Hockney, et. al, for NASA titled, Multiresolution Global Coverage Analysis Using A Point Quad Tree Implementation Of Visual Calculus, began me thinking about more efficient ways to calculate satellite coverage. This article lays out the basic concept, but is very light on details as to where the efficiencies actually come from. The basic idea is to use a quad-tree to compress the storage requirements for maps that define the coverage areas of satellites. In addition, the operations (the computational geometry portion of this treatise) deal with the ability to manipulate these maps in an efficient manner. What I was missing in their article was the efficiency at examining the satellite-earth geometry. The idea behind a quad tree is that each node of the tree represents a large square area of the map subdivided into four equal square. If all of the points (characteristics, etc.) within a sub-area share the same characteristics, then this area need not be further examined and subdivided. If it does contain the characteristics desired, then the area is further subdivided into four smaller squares. The same evaluation process takes place. This creates a situation such as shown below: 
The image shows how the squares are more frequent around the circle boundary. This shows that much of the area has no change, but the boundaries have increasing resolution to describe the change from the white area to the circle. In a similar manner, the circle can represent a satellite coverage area. While this does save on storing information about the location of a boundary between satellite coverage and no satellite coverage, it does not resolve how to determine the coverage area without having to check all of the points. At this time, I have not exactly figured out an efficient way to perform this, but here is an outline of my attack. The satellite nadir, or sub-point, is the center of its coverage area. The coverage radius indicates the distance to the satellite “edge of coverage”. Each square (assuming they are square for the moment) has a center point and a coverage radius. If the distance between the square center point and the coverage center point minus the coverage radius, is less than the radius of the square, then the satellite covers the square for this node of the tree. If so, this node is tagged for further sub-division, otherwise the satellite does not cover this subsquare, and no further examination of this region is needed. This means that the algorithm will calculate more points around the edge of coverage just as shown in the circle diagram. Furthermore, for many satellites this coverage area is constant across a sphere and a simple translation of the quad tree may be used to define the coverage region when the satellite moves to another location. This translated tree combined (i.e., using computational geometry) can use boolean operations to define overall coverage regions. If this works, it is a neat trick! This promises to be a very fast efficient way to calculate the coverage of LEO satellite constellations that involve large numbers of satellites. I have already tried a brute force method for this in Matlab, and it is intensly slow. As I develop the algorithm, I will post more about the results.
