A new framework is introduced to analyze the spatial distribution of stars in a catalog, namely the Voronoi diagram/Delaunay triangulation. The Voronoi diagram is a partition of the celestial sphere into polygonal cells, one for each star, so that the cell for star P consists of the region on the sphere closer to P than to any other star. The Delaunay triangulation is the topological dual with the important property that each spherical cap circumscribing a triangle contains no stars in its interior. Measures of the uniformity in star density and geometric spacing based on the Voronoi diagram/Delaunay triangulation are presented and compared with existing measures. Methods to generate uniformly distributed points on the sphere, which serve as usefiil test cases for stellar attitude determination analysis, are formulated and compared. One such method, based on a spherical spiral, is easy to implement and yields a very uniform distribution of points. Finally the Voronoi density reduction method is introduced to select stars for an on-board catalog from a larger candidate set. The candidate with the smallest Voronoi cell is removed and the Voronoi diagram of the reduced set is constructed. This process is repeated until the desired number of stars remains.