Competitive Analysis of Geometric Search Algorithms

This direction is split into other directions: competitive ratio optimization. Its last version stays readable and citable here.

Version 1 of 120 papers26 conceptsfrozen 2026-10-04

Imagine you are standing in an infinite field, and somewhere in the distance is a hidden treasure. You don't know the direction, and you don't know the distance. If you walk in a straight line and miss it, you might walk forever. If you circle around your starting point too slowly, you waste time. This is the core dilemma of online search theory: how can an agent find a target with unknown coordinates while minimizing the "regret" of not knowing where it was from the start?

To measure success, researchers use the competitive ratio. This metric compares the distance a searcher travels to the distance an "omniscient" agent (who knows the target's location) would have traveled. The goal is to design strategies where this ratio is bounded by a constant, regardless of where the target is hidden.

The Geometry of Uncertainty

The most fundamental version of this problem is the "cow-path problem," where a searcher looks for a point on a line. To ensure the competitive ratio stays small, the searcher must oscillate back and forth, increasing their reach each time.

Daniel S. Bernstein, Lev Finkelstein, and Shlomo Zilberstein demonstrated in Contract Algorithms and Robots on Rays: Unifying Two Scheduling Problems that this geometric intuition extends far beyond simple paths. They proved a formal equivalence between searching on intersecting rays and scheduling "contract algorithms"—programs that must be told their running time in advance. In both cases, the optimal strategy involves a geometric expansion: searching each ray (or running each algorithm) to a depth that increases by a constant factor in each iteration.

When the search space expands to a 2D plane, the "zig-zag" becomes a spiral. Caleb Jones and Matthew Madej explored this in Spirals and Beyond: Competitive Plane Search with Multi-Speed Agents, showing that while a logarithmic spiral is often optimal for a single agent, a team of agents with different speeds requires a hybrid approach. Instead of all following the same path, the agents must divide geometric tasks to maintain an efficient collective competitive ratio.

Searching with Imperfect Information

In many real-world scenarios, finding the target isn't a binary "yes/no" event. Sometimes detection is probabilistic, or the goal is to find multiple items.

Anthony Bonato, Pawel Pralat, and Calum MacRury addressed the "faulty" searcher in Probabilistically Faulty Searching on a Half-Line. They found that if a searcher might walk over a target without seeing it, the standard "monotone" strategy (always moving further out) fails. Instead, the searcher must use "sub-monotone" algorithms—local oscillations that revisit areas multiple times to boost the cumulative probability of detection.

Similarly, Spyros Angelopoulos and Konstantinos Panagiotou generalized the problem to Weighted online search. Here, the searcher must collect targets with different weights until a threshold $W$ is reached. Their work shows that even when the number of targets and their weights are unknown, adaptive strategies can achieve a competitive ratio that matches the single-target case. Surprisingly, as the requirement $W$ grows, the searcher actually becomes more efficient relative to an omniscient opponent because the "luck" of the opponent's prior knowledge is diluted over more targets.

The Searcher versus the Hider

When the target is not placed randomly but is hidden by an adversary, search theory becomes a zero-sum game. The "Hider" wants to place the object in a spot that maximizes the "Seeker's" travel time.

Robbert Fokkink and Thomas F. Lidbetter provided a powerful framework for this in Submodular Search is Scheduling. They modeled the search as a game where the optimal hiding strategy is constrained by the "base polyhedron" of the searcher's cost function. By viewing search through the lens of polyhedral combinatorics, they showed that even NP-hard search problems can be approximated by finding a minimax equilibrium—a strategy that is robust against the worst-case distribution of targets.

This game-theoretic view is essential when resources are strictly limited. Agustín Caracci and José Verschae studied Randomized Binary and Tree Search Under Pressure, where the searcher has a budget smaller than the standard $O(\log n)$ queries. In these "high-pressure" scenarios, a deterministic guarantee is impossible. The solution lies in a randomized Nash equilibrium that maximizes the probability of success, effectively gambling on the target's location in a way that an adversary cannot exploit.

Why Geometric Strategies Work

The recurring success of geometric expansion (doubling distances, logarithmic spirals, up-zig-zags) across these papers stems from a simple intuition: scale invariance.

Because the searcher does not know the distance $d$ to the target, they must hedge their bets across all possible scales. If they increase their search radius too slowly, they spend too much time near the origin. If they increase it too quickly, they might overshoot the target by a massive factor, leading to a huge return trip. A geometric progression ensures that no matter where the target is, the total distance traveled is always a constant multiple of $d$. Whether evacuating a disk Jurek Czyzowicz et al., 2015 or performing group testing Jun Wu et al., 2023, the geometry of the search path is the searcher's primary tool for managing the cost of the unknown.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_competitive_analysis_of_geometric_search_67d80e18,
  title = {Competitive Analysis of Geometric Search Algorithms},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/competitive-analysis-of-geometric-search-algorithms/rdr_67d80e186514465da5a85e014cbb2f66},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_competitive_analysis_of_geometric_search_67d80e18_v1,
  title = {Competitive Analysis of Geometric Search Algorithms},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/competitive-analysis-of-geometric-search-algorithms/rdr_67d80e186514465da5a85e014cbb2f66/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}