Segment-Delta: Exact and Scalable Replacement Refinement for Trajectory Simplification

Fixed-budget trajectory simplifiers produce compact anchor subsequences, but reconstruction quality depends jointly on all anchors, so their outputs may still admit beneficial same-budget replacements. Exhaustively finding the best such replacement requires evaluating $(k-2)(n-k)$ delete–insert pairs at every refinement round. We introduce Segment-Delta, an exact compiler for this complete neighborhood under segment-local reconstruction objectives. Deleting an anchor merges two adjacent intervals, whereas inserting a point splits one; the effects compose when their supports are disjoint, and only a linear number of pairs overlap. Segment-Delta summarizes the disjoint pairs and evaluates the exceptions, reducing candidate comparison in each scan to $O(n+k)$ values. Direct deltas handle additive costs, while a two-pass value–witness procedure handles bottleneck objectives. In exact arithmetic, both recover the same tie-broken move, refinement path, and terminal subset as exhaustive search. After refinement restricted to overlapping edit supports, a complete-neighborhood audit finds a further improving move in 59.7% of 144 terminal states. Across GeoLife and Porto, complete refinement improves classical and learned simplifications and closes 94.2–99.9% of the aggregate Linear dynamic-programming gap for learned constructors. Segment-Delta gives 1.10–1.54$\times$ complete-refinement speedups on published length-1,000 low-retention outputs and 2.11–5.55$\times$ on nested-length complete-path tests ($n\le 96$). With a frozen global Transformer, structurally ranked proposals retain 91.3–98.3% of complete-refinement gain, and every accepted move is verified on the full objective.