Papers

Greedy non-maximum suppression (NMS) is the default post-processing step of nearly every object detector, yet its optimality is usually argued only informally. We give an exact analysis. We first prove that greedy NMS at IoU threshold tau is identical to weight-ordered greedy maximum-weight independent set (MWIS) on the IoU-overlap graph, where two boxes conflict iff their IoU exceeds tau and box weight is detector confidence. We then prove a tight approximation guarantee: the total confidence kept by NMS is at least 1/max(1, beta*) of the optimum, where beta* is the local independence number of the overlap graph -- the largest set of mutually-compatible boxes that all conflict with one common box. We show this bound is tight by explicit constructions. Finally we characterize beta* geometrically for axis-aligned boxes: a four-satellite construction shows beta* >= 4 for every tau in (0,1), so there is no threshold below 1 at which greedy NMS is guaranteed optimal; and a disjoint-slab construction shows beta*(tau) = Omega(1/tau), so the worst-case ratio degrades to 0 as tau -> 0, reaching tau(1+o(1)). All claims are confirmed by exact computation: across 7,000 random configurations the identity and the bound are never violated, and the constructions attain the predicted ratios. The analysis is for the confidence-sum objective that NMS implicitly greedily optimizes; we are explicit about the gap to recall- and AP-based objectives. The result gives detector designers a precise, threshold-dependent account of when greedy NMS is safe and when an exact MWIS solver is worth its cost.