In the second approach we search an image for constrained n-star shapes and match them to similar shapes in a pre-computed table. We show that by using constrained shapes we can reduce the time to match n-star shapes to the order of matching arbitrary 4-star shapes.Finally, we perform experiments on synthetic and real catalogs and show that both approaches perform well.In the 'lost-in-space' astronomy problem we are asked to identify the orientation and field-of-view of an image of the sky by matching stars in an image to stars in a catalog. In this work we present two solutions to the problem.In the first approach we reduce an image to coarse positional information represented by a bit-string. We show that by making one assumption about the image we can efficiently solve the orientation problem using bitwise logical operations over an index.