Provably Optimal Planar Pareto Nearest Neighbor Search with Double Monotone Chains

Abstract

A core task in EDA is to bridge layout and topology: given planar pins, build a sparse graph that captures who should connect to whom, and then optimize on that graph. In timing-driven routing (e.g., Prim–Dijkstra), this means linking each point to its layout nearest neighbors. The right, metric-agnostic choice is the four-quadrant Pareto/skyline neighbors, which preserve candidates for any distance model—but their standard construction has a quadratic time complexity. We introduce a novel double-monotone-chain sweep algorithm that computes all Pareto neighbors in optimal, output-sensitive time O(sum i=1^n ki) and O(n) space where n is the number of points and ki is the number of Pareto neighbors reported for point i. This removes the O(n^2) barrier while retaining full Pareto coverage. On large nets, our implementation produces Steiner trees with OpenROAD-level quality yet runs up to 39× faster. The resulting primitive is a practical gateway from geometry to topology that benefits layout-aware optimizations.