## 2 The Beginning  
After the first CCD-based star tracker was developed by [PERSON] in 1976 at JPL [4], [PERSON], [PERSON], [PERSON] [5; 6], and others began work on implementing an algorithm that could identify stars in real-time. While they realized the benefit of using the easily-computable sine of inter-star angles as a pattern feature, the key problem that arose was the matching of observed inter-stars to the items in the database. After several years of work and a few conference papers, [PERSON] _et al_. published \"_Star Pattern Recognition and Spacecraft Attitude Determination_\" in 1981 [7]. Although the algorithm was able to identify star triplets, it had the primary limitation of requiring an _a priori_ estimate of the spacecraft's attitude before it was able to perform in real-time. The reason is that [PERSON] had used \"sub catalogs\" of the sky, illustrated in Figure 3, each representing a portion of the sky, in order to accelerate the computation. Although the method was robust to non-stars because the catalog included all combinations of stars that might be observed, it only updated the attitude estimation algorithm once or twice a minute, as contrasted with the angular rate sensors, which updated at \(1,000\) times per minute. The majority of the attitude estimation was propagation of the angular rate sensors, and periodic checks were established to confirm and improve the propagated attitude. [PERSON] feature extraction runs very fast, in \(O(b)\) time, since it may select any three of the observed stars and measure the sine of their inter-star angles. However, since his database search considers every possible permutation of stars available in a given region of sky, the search time is \(O(f^{3})\), where \(f\) is the number of stars in a given sub-catalog, usually the same size of a given field of view. The time to perform Star-ID increases if the stars are not located in the predicted field of view as other sub-catalogs are searched. The database itself would grow as \(O(nf^{2})\). In 1986, [PERSON] [8] suggested that a faster way to search the sub-catalogs would be to sort the triangles sides in order based on permutation-invariant values such as the logarithm of the perimeter of a triangle. He admits, however, that his algorithm runs at high polynomial power of \(n\), much as [PERSON] has. [PERSON]'s algorithm differs in that the performance has a lower constant factor. While the asymptotic order of the database is identical to [PERSON], there would be more data included, associated with the permutation-invariant values. In 1987, [PERSON] [9] and others published a patent showing how to improve the search time by using the area of a star triangle and the sum of the luminous intensities as preliminary markers in performing the star identification, using \(O(b)\)-time for star feature extraction. His method does not discuss the way in which the database is searched, requiring only that a \"number of stars\" will be selected from the database by a method using \"parallel, serial, or the like\" processors. It is not noted whether his database indeed contains as many star triplets as does [PERSON] method, nor is the search procedure described. Later, in 1989, [PERSON] [2] suggested in his dissertation that the speed of the star pattern recognition algorithm could be improved by making more use of the available information in the star patterns. [PERSON] discussed directly the relationship between the number of stars and the amount of information available from a star pattern with a given number of stars. His analysis also included a very detailed statistical probability that a star had been identified correctly. Unfortunately, [PERSON]'s method sometimes required the spacecraft to slew in order to detect stars for his Star-ID method, and as such, his work is not covered in depth here.