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.
\(k \ge 3\) robots, known distance
verifiedKnowing \(d\) does not help \(k \ge 3\) robots: the optimal ratio is still exactly \(\sec(\pi/k)\).
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Number of robots: any \(k\)
- \(k \ge 2\) robots; bounds are stated as functions of \(k\).
- Knowledge of the distance: \(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\).
- 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
\(k \ge 3\) robots that know \(d\) (not the direction of the target); the targets are the points of the circle of radius \(d\) about the origin.
What is known
- deterministic
- \(k \ge 3\), targets on the circle of radius \(d\), \(d\) known
- for \(k \ge 4\) a direct argument: at any time \(T < d/\cos(\pi/k)\) some open cone of angle \(2\pi/k\) at the origin holds no robot, and no robot has touched the line tangent to the circle on its bisector
- for \(k = 3\) from Theorem 1 of Dobrev et al. 2020b (shoreline search at known distance, bound 2)
Results, in order of publication
The expanding \(k\)-gon of the unknown-distance setting; it does not use \(d\) (Theorem 4.1).
Open questions
None recorded for this variant.
Notes
From the preprint Kranakis 2026, read in full (arXiv v1).
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.