Too Many Places to Look. So Look at Fewer.
Imagine a set of dots floating over an endless city grid. Each dot needs its own parking space, and the goal is to move all of them as little as possible. The obvious problem: there are infinitely many spaces you could consider. Yu Gao's 2026 result shows that, in 2D, almost all of them can be ignored. Play with the demo first. The math is underneath when you want it.
Everyone needs a unique spot
Two dots cannot end in the same grid location. A locally sensible move for one dot can make the overall answer worse.
Ignore almost the whole grid
In 2D, Gao proves you only need a number of serious destination choices proportional to the number of dots.
What happens in 3D?
Add height and the simple search neighborhoods become cubes. Gao leaves the equally compact higher-dimensional version as an open question.
2D — find everyone a spot
Blue dots start wherever they happen to land. Green marks are legal grid locations. Press Animate and watch the system give every blue dot its own destination while trying to keep total movement low. This demo uses a simple local search window for teaching; Gao's paper uses a smarter proof to shrink the search.
Nearest is easy. Coordinating everyone is hard.
If every dot simply grabs its nearest grid point, two dots may choose the same place. So the system has to make tradeoffs: one dot may travel a little farther so that everyone, collectively, travels less.
The Simple approach makes choices one at a time. Best total movement considers the assignments together. That is why the red paths can look less obvious locally but still be better overall.
Gao's bigger insight: you do not have to search an infinite grid to find the best answer. In 2D, you can throw away almost the entire search space first.A new result built on an old kind of problem: put things in legal places without moving them too far.
The name is modern, but the basic idea is familiar. Computer scientists have long studied how to pair objects efficiently. Chip designers have long needed to move planned components into legal manufacturing positions. Map designers sometimes move real geography onto tidy grids. Gao's 2026 paper brings those ideas to a particularly awkward version of the problem: the possible destinations never end.
Faster ways to pair points
Researchers improve algorithms for matching one set of points to another while keeping total distance small. Think of this as the finite, two-list version of the problem.
Maps make the idea easy to see
Grid-map work assigns geographic regions to tidy cells while trying to keep them near their real-world locations. One region, one cell, as little distortion as possible.
Chip placement becomes a close cousin
Chip-design tools routinely start with ideal positions, then move components into legal, non-overlapping slots. The goal is familiar: obey the rules without disturbing the plan too much.
3D chips make grid placement very real
Modern chip packaging creates dense arrays of terminals, bumps, and pads that must land on legal manufacturing sites without collisions. Small placement errors can matter.
The breakthrough: stop looking almost everywhere
A straightforward safe method can leave you with roughly a square-growth search space. Gao proves that in 2D the serious destination choices can be reduced to a number proportional to the number of input points — without losing the best solution.
Historical framing follows Gao's related-work discussion and cited application literature. See §1.3 of the paper →
The same pattern appears whenever a good plan has to be snapped onto a real grid.
The recipe is surprisingly common: something has an ideal location, the real world offers only certain legal spots, two things cannot use the same spot, and moving too far has a cost. Here are a few places that pattern appears.
Hybrid bonding, bumps & pads
Planned terminal locations from routing or placement must be legalized onto manufacturable grid sites. Two terminals cannot occupy the same site, and displacement matters.
Model: planned terminal → unique manufacturing site; minimize total movement.Standard-cell placement
Integrated-circuit placement often begins continuously and then has to move cells into legal, nonoverlapping positions while limiting displacement.
Model: continuous placement → unique legal slot; minimize legalization cost.Geographic grid visualization
A map can be converted into a regular grid while trying to keep each region near its geographic position and guaranteeing one region per cell.
Model: geographic centroid → unique grid cell; preserve spatial proximity.Warehouse & facility slotting
As a mathematical abstraction, similar assignment logic can model items, robots, or work units choosing distinct discrete slots when Manhattan travel is a meaningful cost.
Important: this is an inferred analogy, not an application claimed by Gao's paper.Screen & dashboard layout
Objects with preferred coordinates can be snapped to a collision-free visual grid while minimizing how far the final layout drifts from the original positions.
Important: conceptual extension; real layout systems usually add many extra constraints.Obstacles, capacities & periodic sites
Gao explicitly points to other periodic target sets plus capacity and obstacle constraints as natural next questions, suggesting a wider family of constrained-placement problems.
Frontier: preserve small candidate sets even after the legal-site rules get more realistic.Direct applications and research extensions: Gao 2026, related work and conclusion →
Searching fewer places can change the problem from “gets ugly fast” to “keeps scaling.”
Move the slider. This is not a stopwatch benchmark; it is a picture of how the amount of work grows. The older safe approach can make the list of possible destinations grow roughly with the square of the input. Gao's final result keeps that list proportional to the number of points.
How many places do we need to consider?
Compare a broad safe search, Gao's intermediate step, and the final linear-size result.
For technical readers: complexity details
Complexity claims are from Gao 2026. The numeric bars intentionally suppress unknown big-O constants and polylog factors; they visualize asymptotic growth, not measured runtime. Read the algorithmic comparison →
One extra dimension changes the shape of the search.
In 2D, a nearby search area is a square. In 3D, it becomes a cube. That means the number of nearby grid locations can grow much faster as you widen the search.
This does not mean 3D is impossible. It means Gao's beautiful 2D compression guarantee does not automatically carry over. His paper explicitly leaves the higher-dimensional version as an open question.
The executive version: 2D has a proof that the search can stay small. In 3D and above, finding an equally strong shortcut is still open.