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 measuresexpand
\(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.
Two robots, unknown distance
standard settingverifiedTwo 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).
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Number of robots: two robots
- Two robots; the visible set at each time is the one segment between them.
- Knowledge of the distance: \(d\) unknown
- The trajectories do not depend on \(d\); the ratio is the supremum over all targets \(x \ne O\) of \(T(x)/\|x\|\).
- Faults: no faults
- Every robot detects and reports the target.
- Speeds: equal speeds
- All robots move at most at unit speed.
- Randomness: deterministic
- Trajectories are fixed functions of the information received.
Statement for this variant
Two robots; the trajectories do not depend on \(d\), and every \(d > 0\) is possible.
What is known
- deterministic
- targets on the three circles of radii \(1/8\), \(1/4\) and \(1\) about the origin; holds even if the robots know these three radii
- any two 1-Lipschitz trajectories (no symmetry assumed)
- scale-invariant: also with circles of radii \(1\), \(2\), \(8\), so it holds when \(d \ge 1\) is promised
Results, in order of publication
Introductory and current best (Theorem 3.1): the robots follow two antipodal logarithmic spirals, so the visible segment is a diameter turning about the origin while it grows; ratio \(e^{\pi\lambda}\sqrt{1+\lambda^2}/\lambda\), minimised at \(\pi\lambda^*(1+\lambda^{*2}) = 1\), \(\lambda^* \approx 0.2931\). Optimal only within this family of spirals.
Open questions
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.
Notes
From the preprint Kranakis 2026, read in full (arXiv v1). The known-distance optimum \(1+\sqrt3+\pi/6\) is a lower bound here as well; the point of Theorem 3.2 is that the unknown distance costs strictly more. With a promised lower bound on \(d\) the spiral needs a finite start, whose ratio the paper does not analyse. For comparison, two robots looking for a line (shoreline search) at unknown distance reach about \(5.2644\) with two equally spaced logarithmic spirals (Baeza-Yates and Schott, as reported by Dobrev et al. 2020b); a line is touched no later than its tangency point is seen, so that bound does not carry over to segment search.
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.