How Satellite Collision Prediction Works: SGP4, TLEs, and KD-Trees

OrbitGuard screens 14,368 active objects against each other in 5.8 seconds. On February 9, 2026, it found 441 real collision risks in a single 24-hour window. How does it work? This post is a technical deep-dive into the algorithms behind satellite collision prediction — from raw TLE data to actionable close approach alerts.

If you're an engineer building space situational awareness (SSA) tools, or an operator who wants to understand what's happening under the hood of your conjunction assessment service, this is for you.

The Pipeline: From TLEs to Close Approach Data

Satellite collision prediction follows a pipeline with four stages:

1. Data ingestion: Fetch TLEs from Space-Track.org
2. Orbit propagation: Compute future positions using SGP4
3. Spatial filtering: Find nearby pairs efficiently using KD-trees
4. Close approach refinement: Compute precise miss distances and timing

Let's examine each stage in detail.

Stage 1: TLE Data and Its Accuracy Limits

A Two-Line Element set (TLE) encodes a satellite's orbit in two 69-character lines. The format dates to the 1960s punchcard era and is still the primary distribution format for the public catalog.

ISS (ZARYA)
1 25544U 98067A   26040.51782528  .00016717  00000-0  10270-3 0  9003
2 25544  51.6400 208.9163 0006703  35.5127 324.6211 15.50103940442678

Each TLE contains:

• Epoch: The time at which the orbital elements are valid
• Mean motion (revolutions per day) and its derivatives
• Eccentricity, inclination, RAAN, argument of perigee, mean anomaly
• B* drag term: Atmospheric drag coefficient in the SGP4 model

TLE Accuracy: The Fundamental Limitation

TLE accuracy is the single biggest constraint in collision prediction. Understanding its limits is essential for interpreting satellite close approach data.

At epoch (the time the TLE was generated), typical position accuracy is:

• LEO (< 2000 km): 0.5-3 km (1σ) for well-tracked objects
• Small objects (CubeSats): 1-5+ km due to less frequent tracking
• GEO: 1-5 km, but lower relative velocities mean more time to refine

Accuracy degrades rapidly as you propagate forward from epoch. After 24 hours, LEO position errors can grow to 5-15 km. After 3 days, errors of 20-50+ km are common. This is because TLEs use mean elements with simplified perturbation models — atmospheric drag variations, solar radiation pressure, and gravitational harmonics all introduce drift.

TLE Freshness Matters

OrbitGuard always uses the most recent TLE available for each object. The age of a TLE — the time between epoch and the prediction time — directly impacts accuracy. Our screening runs use the following heuristic:

• TLE age < 24h: High confidence — use standard screening thresholds
• TLE age 1-3 days: Moderate confidence — widen screening volume
• TLE age > 3 days: Low confidence — flag results as degraded

Stage 2: SGP4 Orbit Propagation

SGP4 (Simplified General Perturbations 4) is the analytical propagation model designed to work with TLE mean elements. It was developed by the U.S. Air Force in the 1960s-70s and remains the standard for TLE propagation.

What SGP4 Models

SGP4 accounts for:

• Earth's oblateness (J2, J3, J4 zonal harmonics) — the equatorial bulge causes orbit plane precession and argument of perigee drift
• Atmospheric drag — modeled via the B* term, causing orbital decay
• Solar/lunar gravitational perturbations (SDP4 variant for deep-space objects)

What SGP4 Doesn't Model

SGP4 is intentionally simplified. It omits:

• Tesseral harmonics: Longitude-dependent gravity variations
• Solar radiation pressure: Significant for high area-to-mass ratio objects
• Atmospheric density variations: Solar activity causes order-of-magnitude changes in drag
• Maneuvers: SGP4 has no concept of thrust events

These omissions are why TLE accuracy degrades over time. For higher-fidelity prediction, you'd use numerical propagation with force models like those in NASA ODPO's tools or ESA's DRAMA suite. But for catalog-wide screening where you need to evaluate billions of potential pairs, SGP4's analytical speed is essential.

Batch Propagation: The Performance Challenge

To screen 14,368 objects over a 24-hour window, you need to propagate every object at multiple time steps. OrbitGuard uses batch SGP4 propagation — computing positions for all objects at each time step in a single vectorized operation.

The key optimization is treating propagation as a matrix operation rather than 14,368 individual function calls. Using NumPy/CuPy array operations:

# Pseudocode for batch propagation
# All 14,368 TLEs propagated at once per timestep
for t in time_steps:        # e.g., every 60 seconds over 24h
    positions = sgp4_batch(all_tles, t)  # Returns (N, 3) array
    # positions is now a 14368 x 3 matrix of ECI coordinates
    tree = KDTree(positions)
    pairs = tree.query_pairs(threshold_km)
    close_approaches.extend(pairs)

The time step interval is a tradeoff: smaller steps catch more conjunctions but increase computation. OrbitGuard uses adaptive stepping — coarser intervals (5 minutes) for the initial scan, then refining to 10-second steps around detected close approaches.

Stage 3: KD-Tree Spatial Indexing

This is where OrbitGuard gets its speed. The naive approach to all-vs-all screening is O(n²) — with 14,368 objects, that's 103,199,456 pair comparisons per time step. At dozens of time steps per day, this becomes billions of distance calculations.

KD-trees (k-dimensional trees) are spatial data structures that partition 3D space into a binary tree, enabling nearest-neighbor queries in O(n log n) instead of O(n²).

How KD-Tree Screening Works

At each time step:

1. Build the tree: Insert all object positions (ECI x, y, z coordinates) into a KD-tree. This is O(n log n).
2. Query pairs: Ask the tree for all pairs within a threshold distance (e.g., 50 km). The tree prunes vast regions of space that can't contain matches, reducing comparisons dramatically.
3. Collect results: Only pairs within the threshold are returned for further analysis.

# Using scipy's cKDTree (C implementation)
from scipy.spatial import cKDTree

tree = cKDTree(positions)  # positions: (14368, 3) in km
pairs = tree.query_pairs(r=50.0)  # All pairs within 50 km

# Returns set of (i, j) index tuples
# Typical result: hundreds of pairs out of 103M possible

The performance gain is enormous. Instead of checking 103 million pairs, the KD-tree typically evaluates a few hundred thousand distance comparisons — a 100-1000x speedup.

Why 5.8 Seconds Is Possible

OrbitGuard's 5.8-second screening time combines three optimizations:

1. Batch SGP4: Vectorized propagation for all objects simultaneously
2. KD-tree indexing: O(n log n) spatial filtering instead of O(n²)
3. Adaptive time stepping: Coarse scan first, refine only around detections

This runs on consumer hardware — the benchmark was performed on a NVIDIA Jetson Orin Nano, a $250 single-board computer with a modest GPU. No supercomputer required.

Stage 4: Close Approach Refinement

After spatial filtering identifies candidate pairs, each pair needs precise close approach characterization:

Time of Closest Approach (TCA)

The coarse time step that detected the pair gives an approximate TCA. Refinement uses bisection or Newton's method on the distance function between the two objects, finding the exact time of minimum separation to sub-second precision.

Miss Distance

The miss distance is the minimum distance between the two objects at TCA. It's computed in the radial-along-track-cross-track (RIC) reference frame, which separates the miss into physically meaningful components:

• Radial (R): The difference in orbital altitude at TCA
• In-track / Along-track (I): The timing difference — how far ahead or behind one object is
• Cross-track (C): The perpendicular distance between orbital planes at the conjunction point

In-track uncertainty is typically the largest component (because timing errors dominate), while cross-track separation is often the most stable and meaningful predictor of actual risk.

Relative Velocity

The relative velocity at TCA determines the energy of a potential collision and the geometry of the conjunction. OrbitGuard's February 9, 2026 screening found relative velocities up to 11.55 km/s — these are near-perpendicular conjunctions where objects cross orbital planes at steep angles. The highest-velocity conjunctions are also the hardest to avoid because they allow the least warning time.

Filtering: Separating Signal from Noise

Raw conjunction screening produces many results that aren't actual collision threats. Intelligent filtering is critical to reduce operator workload.

Co-Location Filtering

Satellites in the same constellation (e.g., Starlink trains, Planet Doves) are intentionally close to each other. These co-located formations appear as "conjunctions" in naive screening but aren't threats.

OrbitGuard detects co-located formations by identifying clusters of objects with similar orbital elements (semi-major axis, inclination, RAAN) and low relative velocities. On February 9, 2026, 174 co-located formations were detected and filtered, significantly reducing false positives.

Same-Object Filtering

Some objects have multiple catalog entries (e.g., analyst satellites or recently correlated debris). These must be detected and deduplicated.

Threshold-Based Prioritization

Not all close approaches deserve the same attention. OrbitGuard categorizes conjunctions by miss distance and relative velocity:

• Critical (< 1 km): Immediate alert — maneuver decision required
• Warning (1-5 km): Elevated monitoring, begin maneuver planning
• Watch (5-25 km): Track and reassess as TLEs update
• Monitor (25-50 km): Log for situational awareness

Probability of Collision: Beyond Miss Distance

Raw miss distance is insufficient for decision-making. A 2 km miss distance with 500-meter position uncertainty is far more dangerous than a 2 km miss distance with 10 km uncertainty (the latter means the objects probably aren't that close at all).

The probability of collision (Pc) combines miss distance with position uncertainty:

The 2D Pc Approach

The standard method (Foster/Chan) projects the 3D covariance ellipsoids of both objects onto the conjunction plane (perpendicular to the relative velocity vector). In this plane:

1. Combine the position covariance matrices of both objects
2. Define a "hard body" circle with the combined physical radii
3. Integrate the 2D Gaussian probability density over the hard body circle

# Simplified Pc calculation concept
import numpy as np
from scipy.stats import multivariate_normal

def compute_pc(miss_vector_2d, combined_covariance_2d, hard_body_radius):
    """
    miss_vector_2d: [x, y] miss distance in conjunction plane (km)
    combined_covariance_2d: 2x2 combined covariance matrix (km²)
    hard_body_radius: combined object radii (km)
    """
    # Create 2D Gaussian with combined covariance
    rv = multivariate_normal(mean=miss_vector_2d, 
                             cov=combined_covariance_2d)
    
    # Integrate over hard body circle
    # (In practice, use analytical or numerical integration)
    # Foster's method uses series expansion
    # Alfano's method uses numerical quadrature
    
    return pc  # Probability value, typically 1e-10 to 1e-2

Covariance Data: The Missing Piece

Here's the challenge: TLEs don't include covariance information. The covariance matrices needed for Pc calculation are only available in Conjunction Data Messages (CDMs) from Space-Track.org, or from operator-generated ephemerides.

Without covariance data, you can estimate position uncertainty based on TLE age and object characteristics, but these estimates are approximate. This is one reason why CDM-based conjunction assessment (from the 18th Space Defense Squadron) remains the gold standard for maneuver decisions.

OrbitGuard's TLE-based screening serves as a first-pass filter — identifying which conjunctions deserve attention and CDM requests. It's complementary to, not a replacement for, CDM-based risk assessment. For a broader overview of the full risk assessment process, see our complete guide to satellite collision risk assessment.

Implementation: How OrbitGuard Is Built

OrbitGuard is open source under the Apache 2.0 license. Here's the technical architecture:

Core Stack

• Python 3.11+ with NumPy for vectorized computation
• sgp4 library (Brandon Rhodes' implementation) for orbit propagation
• scipy.spatial.cKDTree for spatial indexing
• Optional: CuPy for GPU-accelerated batch propagation on CUDA hardware

Data Flow

1. Fetch latest TLEs from Space-Track.org API
2. Parse and validate TLEs, filter by active status
3. Batch propagate all objects at each time step
4. Build KD-tree, query for pairs within threshold
5. Refine close approaches with sub-second TCA resolution
6. Filter co-located formations and duplicate catalog entries
7. Classify, prioritize, and output results

Performance Characteristics

• 14,368 objects screened in 5.8 seconds (Jetson Orin Nano)
• 441 collision risks found per 24-hour window (Feb 9, 2026)
• 174 co-located formations automatically filtered
• Memory usage: ~200 MB peak
• Scales linearly with number of time steps, O(n log n) per step

The source code is on GitHub. Contributions welcome. If you're building SSA tools, the codebase demonstrates practical implementations of batch propagation, KD-tree screening, and co-location detection.

Limitations and Future Directions

Current Limitations

• TLE-only: No support for SP ephemeris or owner/operator ephemeris (yet)
• No covariance-based Pc: Miss distance and relative velocity only — full Pc requires CDM data
• No maneuver detection: Maneuvering satellites may violate TLE predictions
• Catalog completeness: Objects below 10 cm aren't tracked — this is a sensing limitation, not an algorithm limitation

What's Next

• CDM integration: Ingest CDMs for covariance-based Pc calculation
• Maneuver detection: Identify TLE discontinuities that indicate maneuvers
• Orbit determination: Process GPS/ranging data for higher-fidelity orbits
• GPU acceleration: Full CUDA pipeline for sub-second screening

The ESA Space Debris Office and NASA ODPO continue to advance the state of the art in conjunction assessment. The gap between government capabilities and what's available to independent operators is closing — and open-source tools like OrbitGuard are part of that democratization.

For university teams and small satellite operators, these tools make professional-grade collision monitoring accessible for the first time. The algorithms aren't magic — they're well-understood computational geometry applied at orbital scale.