ASQNT: An Adaptive Spherical Quadtree Framework with Negative Feedback for Optimal Navigation Star Selection

Objectives: The exponential growth of Earth observation satellites and deep-space exploration missions has created an unprecedented demand for high-precision autonomous navigation. As the only instrument providing absolute attitude reference, the star tracker is crucial for spacecraft navigation. The core of a star tracker's functionality is its navigation star catalog, whose quality directly determines the system's accuracy and reliability. The fundamental challenge in constructing such a catalog lies in balancing spatial uniformity with computational efficiency, particularly when processing modern, massive stellar databases like Gaia's Early Data Release 3 (EDR3), which contains over 1.8 billion stars. The natural, extreme non-uniformity of stellar distribution across the celestial sphere—varying by four orders of magnitude from the galactic plane to the polar regions—presents a significant obstacle. Existing methods, including magnitude filtering, geometric filtering, and machine learning approaches, suffer from inherent limitations such as spherical projection distortion, static partitioning schemes incapable of adapting to local density variations, and a lack of effective feedback mechanisms for dynamic optimization. This paper aims to address these shortcomings by proposing a novel, self-regulating framework that transforms the star selection problem into a dynamic optimization system, thereby establishing a robust theoretical and practical foundation for next-generation high-precision star sensors. Methods: This paper presents ASQNT (Adaptive Spherical Quadtree Navigation-star Technique), a comprehensive framework built upon four key methodological innovations: (1) Solid Angle-Based Recursive Partitioning Model (SABRM): To eliminate spherical projection distortion inherent in traditional methods (e.g., latitude-longitude grids), a recursive partitioning model based on solid angle equivalence was constructed. The celestial sphere is subdivided into regions of equal solid angle, fundamentally addressing area compression at high latitudes. The mathematical model, derived from integrating the differential solid angle element dΩ = cos(δ)dδdα, ensures that each partition satisfies Ω(R_i) = 1/4 Ω(R). The error bound of this partitioning was rigorously proven to be O(△δ³), ensuring rapid convergence and minimal distortion; (2) Density-Adaptive Quadtree Structure: An adaptive quadtree structure, guided by a dual-factor density-area weighting model, was developed to intelligently adjust partitioning granularity. The local density for a region R is defined as ρR = n_R/Ω_R, normalized by solid angle to ensure comparability across latitudes. A target density ρ_target is calculated based on star sensor parameters (e.g., field-of-view, minimum stars required for identification). A dynamic feedback mechanism triggers further subdivision only when the stellar count n_R deviates from the expected range β_nexp, αn_exp. The weight for child nodes is assigned as wi = n_i/Ω_i/∑⁴ _j=1 n_j/Ω_j, giving higher priority for subdivision to denser regions while naturally creating a negative feedback effect as density equalizes; (3) Negative Feedback Mechanism via Gradient Penalty: A closed-loop optimization system was constructed using a gradient penalty function P(R_i ) based on spatial Markov Random Field theory. This function dynamically penalizes the weights of oversampled regions: P(R_i) = 1 + ∑_j∈N(i) ω_ij · (N_j^selected/N_j^max)², where ω_ij = exp(-d_ij/σ) is a spatial correlation weight. The subsequent weight update W(R_i) = W(R_i)/P(R_i) ensures that sufficiently sampled regions are automatically suppressed, guiding the optimization toward global uniformity; (4) Dynamic Compensation Model for Sparse Regions: To guarantee complete sky coverage without blind zones, a Compensation Model for Sparsely Distributed Regions (CMSDR) was designed. It employs a non-linear expansion mechanism that dynamically adjusts the search range in sparse areas: R_expanded = RA_min - δ, RA_max + δ, DEC_min - δ, DEC_max + δ, where δ = δ_base · exp(k · (1 - ρ_i/ρ_t)). This ensures aggressive searching in extremely sparse regions while maintaining efficiency elsewhere. Combined with a magnitude-priority selection strategy in dense regions (S_selected = s ∈ S_i ∣ mag(s) ≤ mag_thresh ∧ Δθ_ij ≥ θ_min) , it co-optimizes for brightness and uniformity. Results: Comprehensive experiments were conducted on Gaia EDR3 (1.8 billion stars, limiting magnitude ≤ 10) to evaluate ASQNT against six representative algorithms: GABM, SSBK, KNN, ISSM-GRNN, ISSM-ELM, and traditional methods. The target catalog size was set to ~10,000 stars with an 8° field-of-view. ASQNT demonstrates superior performance across all metrics: (1) Spatial uniformity: UI=0.99997, approaching the theoretical limit of 0.99999, with VLU improved by 14.5% over the next-best algorithm. Notably, galactic plane uniformity reaches 0.99992 despite extreme density variations. (2) Field-of-view coverage: ASQNT is the only algorithm achieving 100% coverage with zero blind zones, while others range from 53.27% to 99.79%. The standard deviation of stars per field is the lowest among all methods. (3) Magnitude optimization: 100% of selected stars are brighter than magnitude 7.0 (competitors: 1.61%-23.13%), with an average magnitude of 5.61 versus 9.11 for GABM, ensuring reliability under adverse conditions. (4) Computational efficiency: Processing 15 million stars requires only 32.6 seconds, 6.6× faster than SSBK and orders of magnitude faster than machine learning approaches (ISSM-GRNN: 1255.7s). (5) Polar region performance: 518 polar stars (|δ| ≥ 75°) selected versus 324- 325 for competing algorithms, representing a 59.4% improvement in sparse region coverage. Sensitivity analysis confirms robust performance with parameter variations causing <0.5% UI change. Conclusions: This research establishes, for the first time, a complete mathematical framework based on solid angle equivalence, transforming the empirical star catalog construction problem into an optimization problem with rigorous theoretical guarantees. Key contributions include: (1) proven convergence with bounded iteration depth k_max = log₄ (ρ₀/ρ_target) , (2) information-theoretic optimality through maximizing distribution entropy, and (3) O(n log n) time complexity enabling efficient processing of billion-scale datasets. The innovative design of adaptive quadtree structure and negative feedback regulation mechanism achieves organic unity of local decisions with global optimization. The framework successfully addresses all critical requirements for next-generation high-precision star sensors: spatial uniformity approaching theoretical limits (eliminating systematic bias), complete field-of-view coverage (eliminating recognition blind zones), optimal bright star ratio (ensuring reliability under adverse conditions), and computational efficiency meeting real-time requirements. The algorithm has achieved practical deployment readiness and can be directly applied to new-generation high-precision star sensors, providing technical support for major missions including deep space exploration, high-resolution Earth observation, and autonomous spacecraft navigation. Future work will focus on progressive mesh structures for further polar optimization and incremental update algorithms for on-orbit autonomous catalog maintenance.