Home›Search in geometric domains›Search, evacuation and patrolling›Search with segment visibility

Search with segment visibility

Robots search the plane for a point that they see when it lies on the segment joining two of them.

Problem statement and measurescollapse

\(k \ge 2\) robots of unit speed start together at the origin \(O\) of the plane, share a coordinate frame and a clock, and move deterministically. A stationary target lies at an unknown point \(x \ne O\) at distance \(d = \|x\| > 0\). The target is found at the first time \(t\) at which \(x\) lies on the closed segment joining the positions of two robots at time \(t\); robots learn nothing about the target before. Depending on the setting the robots know \(d\) or not; they never know the direction of \(x\). Time is the competitive ratio: the supremum, over targets, of the time until the target is found divided by \(d\).

Measures: Competitive ratio, worst-case time until the target lies on a segment between two robots, divided by its distance \(d\) from the origin.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Two or more lifeguards scan the sea for a buoy, and a buoy counts as seen as soon as it lies on the line of sight between two of them. Here \(k \ge 2\) robots, points of unit speed, start together at the origin \(O\) of the plane. A target, a point \(x\) at distance \(d\) from the origin, sits in an unknown direction. At every moment each pair of robots sees the straight segment that joins them, and the target is found the first time it lies on such a segment. The robots share a coordinate frame and a clock, and their routes are fixed in advance. The cost of a route plan is its competitive ratio: the largest value, over all targets, of the time until the target is found divided by \(d\). In the basic version two robots do not know \(d\).

1AlgorithmWalk out in \(k\) equally spaced directions \(k \ge 3\) robots, unknown distance → Kranakis 2026

For \(k \ge 3\) robots:

Number the robots \(0, 1, \dots, k-1\).
Robot \(i\) walks straight away from the origin in the direction at angle \(2\pi i/k\), forever.
At time \(t\) the robots are the corners of a regular \(k\)-gon of circumradius \(t\); its sides are segments between neighbouring robots, and they sweep the plane as the polygon grows.

Why it works and what it costs. A target at distance \(d\) whose direction is at angle \(\varphi\) from the middle of its sector lies on a side of the polygon when \(t\cos(\pi/k) = d\cos\varphi\), that is at time \(d\cos\varphi/\cos(\pi/k)\). The worst targets are in the middle of a sector, so the competitive ratio is \(1/\cos(\pi/k) = \sec(\pi/k)\): 2 for three robots, about 1.41 for four, and close to 1 for many robots. Kranakis 2026 proves that no plan does better, whether or not the robots know \(d\).

Why it matters. It is optimal and needs no knowledge of \(d\); the same walk is optimal for robots looking for a line.

2Lower boundSeeing a point is at least as hard as touching its tangent line Two robots, known distance → Kranakis 2026

Take a target \(x\) at distance \(d\) and the straight line through \(x\) that is perpendicular to the direction of \(x\) (the tangent at \(x\) to the circle of radius \(d\) about the origin). The robots start on the origin's side of that line. When \(x\) lies on a segment between two robots, one of the two must be on the line or beyond it.

Why it holds. So a plan that finds every target point of the circle within time \(Td\) also makes some robot touch every tangent line within time \(Td\): it solves shoreline search, the search for a line at known distance. The best ratio for two robots that look for a line at known distance is \(1+\sqrt3+\pi/6 \approx 3.256\) Dobrev et al. 2020b, so no two-robot plan for points does better. Kranakis 2026 gives a two-robot route that reaches exactly this ratio, so the bound is tight. When \(d\) is unknown, the best known two-robot plan, two spirals on opposite sides of the origin, needs about \(8.93\), and the best lower bound is about \(3.29\).

Why it matters. The reduction lets every lower bound for line search transfer to point search with segment visibility, which settles all cases except two robots that do not know \(d\).

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Competitive ratio

Two robots, unknown distance standard

Two robots that do not know \(d\) need a ratio between \(\sqrt3+\pi/6+\sqrt{17}/4 \approx 3.2864\) and \(\approx 8.9285\); the gap is open (a preprint).

polynomial gap \(e^{\pi\lambda^*}\sqrt{1+\lambda^{*2}}/\lambda^* \approx 8.9285\) vs \(\sqrt3+\pi/6+\sqrt{17}/4 \approx 3.2864\) unknown distance

Two robots, known distance

Two robots that know \(d\) need exactly \(1+\sqrt3+\pi/6 \approx 3.2556\), the same ratio as two robots looking for a line at known distance.

tight \(1+\sqrt3+\pi/6\) vs \(1+\sqrt3+\pi/6\) unknown direction

\(k \ge 3\) robots, unknown distance

With \(k \ge 3\) robots the optimal ratio is exactly \(\sec(\pi/k)\): the robots walk straight in \(k\) equally spaced directions and the edges of the growing regular \(k\)-gon sweep the plane.

tight \(\sec(\pi/k)\) vs \(\sec(\pi/k)\) unknown direction

\(k \ge 3\) robots, known distance

Knowing \(d\) does not help \(k \ge 3\) robots: the optimal ratio is still exactly \(\sec(\pi/k)\).

tight \(\sec(\pi/k)\) vs \(\sec(\pi/k)\) unknown direction

Open questions 2

Two robots, unknown distance

Determine the optimal competitive ratio of two robots that do not know \(d\): it lies between \(\sqrt3+\pi/6+\sqrt{17}/4 \approx 3.2864\) and \(\approx 8.9285\) Kranakis 2026.
Do asymmetric, non-antipodal or non-spiral trajectories beat \(\approx 8.9285\)? The antipodal spirals see only along a diameter through the origin, while a segment between two moving robots can sweep chords that miss it Kranakis 2026.

What the community started looking at

Search for a target at an unknown place in the plane goes back to Bellman's question of how to find a line at known distance, and to the search for a line or a point by one or several robots of unit speed Baeza-Yates et al. 1993 Dobrev et al. 2020b. In those models a robot finds the target by touching it. Kranakis lets the robots see along the segments that join them, so a team sees a whole set of chords at each moment, and studies how much this helps; the answers are expressed through shoreline search, whose lower bounds carry over Kranakis 2026.

All settings

The assumption tree (4 settings, 2 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Competitive ratio); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Number of robots › Knowledge of the distance › Faults › Speeds › Randomness.

tight near-optimal polynomial gap unknown impossible no variant

No assumptions · 3 branches by number of robots Nothing is assumed on any axis.
- +two robots
  Knowledge of the distance · 2 branches
  - \(d\) unknown+no faults+equal speeds
    Two robots, unknown distance standard setting Two robots that do not know \(d\) need a ratio between \(\sqrt3+\pi/6+\sqrt{17}/4 \approx 3.2864\) and \(\approx 8.9285\); the gap is open (a preprint).
  - +\(d\) known+no faults+equal speeds
    Two robots, known distance Two robots that know \(d\) need exactly \(1+\sqrt3+\pi/6 \approx 3.2556\), the same ratio as two robots looking for a line at known distance.
- any \(k\)\(d\) unknown+no faults+equal speeds
  \(k \ge 3\) robots, unknown distance With \(k \ge 3\) robots the optimal ratio is exactly \(\sec(\pi/k)\): the robots walk straight in \(k\) equally spaced directions and the edges of the growing regular \(k\)-gon sweep the plane.
- any \(k\)+\(d\) known+no faults+equal speeds
  \(k \ge 3\) robots, known distance Knowing \(d\) does not help \(k \ge 3\) robots: the optimal ratio is still exactly \(\sec(\pi/k)\).

Assumptions specific to this problem

Number of robots

0any number \(k \ge 2\) of robots1two robots

Kranakis treats two robots separately because with two robots there is a single visible segment and the expanding-polygon algorithm does not exist; for \(k \ge 3\) the optimum is \(\sec(\pi/k)\) Kranakis 2026. The same split appears in shoreline search, where the cases \(k = 2\) and \(k = 3\) were the last to be settled for a known distance Dobrev et al. 2020b.

Formal definitions

0any \(k\): \(k \ge 2\) robots; bounds are stated as functions of \(k\).
1two robots: Two robots; the visible set at each time is the one segment between them.

Knowledge of the distance

0\(d\) unknown1\(d\) known

Shoreline search was first studied at a known distance (Bellman's problem, solved for one searcher by Isbell, as reported by Dobrev et al. 2020b); Baeza-Yates, Culberson and Rawlins considered the unknown distance Baeza-Yates et al. 1993 (as reported by Dobrev et al. 2020b). Kranakis distinguishes the same two regimes for segment visibility and shows that for two robots not knowing \(d\) costs at least \(\sqrt{17}/4 - 1 \approx 0.031\) in the ratio, while for \(k \ge 3\) it costs nothing Kranakis 2026.

Formal definitions

0\(d\) unknown: The trajectories do not depend on \(d\); the ratio is the supremum over all targets \(x \ne O\) of \(T(x)/\|x\|\).
1\(d\) known: The robots know \(d\) (not the direction of the target); the trajectories may depend on \(d\), and the ratio is the supremum over targets with \(\|x\| = d\) of \(T(x)/d\).

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.