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, unknown distance
verifiedWith \(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.
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\) 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
\(k \ge 3\) robots that do not know \(d\); every segment between two robots is visible (the algorithm uses only segments between neighbours on the \(k\)-gon). For \(k = 2\) see the two-robot settings.
What is known
- deterministic
- \(k \ge 3\)
- holds even when every segment between two robots is visible
- from shoreline search at unknown distance: Theorem 2.1 of Acharjee et al. 2019 for \(k \ge 4\), Theorem 1 of Dobrev et al. 2020b for \(k = 3\)
Results, in order of publication
Introductory and current best (Theorem 4.1, Lemma 4.2): robot \(i\) walks straight in direction \(2\pi i/k\); a target at angle \(\varphi\) from the bisector of its sector is found at time \(d\cos\varphi/\cos(\pi/k)\), worst on the bisectors. Does not use \(d\).
Open questions
None recorded for this variant.
Notes
From the preprint Kranakis 2026, read in full (arXiv v1). The ratio is the same as the optimum of shoreline search with \(k \ge 3\) robots, whose upper bound \(1/\cos(\pi/k)\) is the same walk along \(k\) equally spaced rays (Baeza-Yates and Schott, as reported by Dobrev et al. 2020b): with three or more robots, seeing a point on a segment costs no more than touching its tangent line.
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
No catalogued weaker setting.
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.