An algorithm searches a star catalog to identify guide stars within the field of view of a telescope or camera. The algorithm is fast: the number of computations needed to perform the search is approximately proportional to the logarithm of the number of stars in the catalog.

A Hierarchy of Sequentially Numbered Elements is created from entries in a star catalog. In this example, the hierarchy is based on nine stars and includes a total of four levels.
The algorithm requires the prior organization of the star catalog into a hierarchy utilizing independent spherical coverings (see figure), such that each successively higher level contains fewer elements. In the lowest and most numerous level of the hierarchy, the elements are individual stars in the star catalog. The next higher level contains a spherical covering (a constellation of n points on a sphere that minimizes the maximum distance of any point on the sphere from the closest one of the n points), the next higher level contains a smaller spherical covering, and so forth, ending at the highest level, which contains one element representing the point of entry into the search structure.

With necessary exceptions at the lowest and highest levels, each element at each level is labeled in terms of the element to which it is linked in the next higher level and the first element to which it is linked in the next lower level. Each element is also labeled in terms of (1) its coordinates on the celestial sphere and (2) the largest angular distance to any element in any lower level in the hierarchy. The elements at all levels of the hierarchy are numbered on a single list, such that the elements of each constellation at each level are numbered consecutively. The algorithm is recursive.

The input required to start the algorithm comprises the coordinates of a point on the celestial sphere. Attention is then focused on individual elements of the hierarchy, starting from the topmost one, as follows: The angle between the input point and the element under consideration is calculated. If the calculated angle is larger than the sum of (1) the predetermined angle to the most distant element plus (2) the half field of view of the telescope, then no stars will be within the field of view and this recursive part of the algorithm is terminated. If the calculated angle is smaller than the afore-said sum, then the focus of attention is shifted to the elements in the next lower level of the hierarchy, in numerical order. The foregoing operations are repeated until either the algorithm is terminated or the focus of attention reaches an element at the lowest level (a star-catalog entry). In the latter case, the star is identified as being in the field of view.

This work was done by Carl Christian Liebe of Caltech for NASA's Jet Propulsion Laboratory.

The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (818) 393-2827. Refer to NPO-40823.


This Brief includes a Technical Support Package (TSP).
Algorithm for Rapid Searching Among Star-Catalog Entries

(reference NPO-40823) is currently available for download from the TSP library.

Don't have an account? Sign up here.