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.

Topics:
Computer software and hardware Electrical systems Imaging and visualization Information Technology Mathematical models Optics Research and development Simulation and modeling Starters and starting Telescopes
This Brief includes a Technical Support Package (TSP).
Document cover
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?

Magazine cover
NASA Tech Briefs Magazine

This article first appeared in the November, 2006 issue of NASA Tech Briefs Magazine (Vol. 30 No. 11).

Read more articles from the archives here.

Overview

The document is a Technical Support Package from NASA's Jet Propulsion Laboratory (JPL) that details an innovative algorithm for rapid searching among star-catalog entries, identified as NPO-40823. This algorithm is part of NASA Tech Briefs and is aimed at enhancing the efficiency of astronomical data retrieval, which is crucial for various applications in aerospace and astrophysics.

The primary focus of the algorithm is to facilitate quick and accurate searches within extensive star catalogs, which are essential for navigation, research, and exploration in space. The document references a related work titled "Fast Spherical Search Algorithm" by C.C. Liebe, presented at the 2004 IEEE Aerospace Conference. This algorithm is designed to optimize the process of searching for celestial objects by employing advanced computational techniques that reduce the time and resources required for such tasks.

The Technical Support Package emphasizes the significance of this algorithm in the context of the Commercial Technology Program of NASA, which aims to disseminate aerospace-related developments that have potential technological, scientific, or commercial applications. The document serves as a resource for researchers, engineers, and industry professionals interested in leveraging this technology for various applications beyond its initial aerospace context.

Additionally, the document provides contact information for further assistance, including access to the NASA Scientific and Technical Information (STI) Program Office, which offers a wealth of resources related to research and technology in this field. The STI Help Desk is available for inquiries, ensuring that users can obtain the necessary support and information regarding the algorithm and its applications.

Overall, the Technical Support Package not only outlines the capabilities of the rapid searching algorithm but also positions it within the broader framework of NASA's commitment to innovation and technology transfer. By making such advancements accessible, NASA aims to foster collaboration and encourage the application of aerospace technologies in various sectors, ultimately contributing to scientific progress and exploration.