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, known distance
verifiedTwo 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.
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\) 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
Two 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
- targets on the circle of radius \(d\), \(d\) known
- any two 1-Lipschitz trajectories
- from shoreline search at known distance (Theorem 3 of Dobrev et al. 2020b): a robot touches the line tangent at the target no later than the target is seen
Results, in order of publication
Introductory and current best (Theorem 2.1, Proposition 2.3): robot \(\sigma \in \{\pm1\}\) walks straight to \((\sigma d/\sqrt3, d)\), along the tangent to \((\sigma\sqrt3 d/2, d/2)\), along the circle to \((\sigma d, 0)\), then straight down to \((\sigma d, -d)\); the last point found is \((0, -d)\).
Open questions
None recorded for this variant.
Notes
From the preprint Kranakis 2026, read in full (arXiv v1). The upper bound is proved directly; the lower bound is Theorem 3 of Dobrev et al. 2020b for shoreline search, transferred by the tangent-line reduction.
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
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.