Searching the Plane in the Segment Visibility Model

Searching the Plane in the Segment Visibility Model Evangelos Kranakis∗ School of Computer Science, Carleton University Ottawa, Ontario, K1S 5B6, Canada

arXiv:2611.03161v1 [cs.DM] 2 Nov 2026

Abstract We study deterministic search by n ≥ 2 unit-speed robots starting at the origin of the Euclidean plane. We introduce the concept of segment visibility whereby a stationary target x at distance d = ∥x∥ > 0 is discovered at the first instant t when x belongs to the segment joining a pair of robots at time t. Discovery time is compared with the omniscient optimum d. We distinguish two knowledge models according to whether the robots know d in advance. For n = 2 robots, in the known-d model, we√give a symmetric four-phase algorithm and prove that its competitive ratio is optimal: CR∗known d = 1 + 3 + π/6; the matching lower bound follows from the known-distance two-robot shoreline-search theorem through an explicit reduction to segment detection. For n = 2 robots, in the unknown-d model, construction and a quantitative initial-path estimate yield the stronger √ a three-circle √ lower bound 3 + π/6 + 17/4 ≈ 3.286425990, giving an explicit positive cost for not knowing the radius; we also analyze a feasible antipodal-diameter logarithmic-spiral algorithm with optimized ratio √ √ 8.928516954 . . ., thus proving 3 + π6 + 417 ≤ CR∗unknown d ≤ 8.928516954 . . . . For n ≥ 3 robots, the competitive ratio of finding the target is exactly sec(π/n) regardless of whether or not d is known to the robots. Key Words and Phrases: Agents, Circle, Competitive Ratio, Plane, Segment Visibility, Robots, Search, Target.

1

Introduction

A team of n robots starts at the origin O of the Euclidean plane and search for a stationary point target x ̸= O. Each robot moves at speed at most one. The target is found precisely when at least one instantaneous closed segment joining a pair of robots contains x. All pairwise segments are visible in the base model. Unlike search by one observer whose visible segment has the origin as a fixed endpoint, both endpoints here may move independently, and the connecting segment may pass through points never visited by either robot. Write d = ∥x∥ > 0 for the target’s distance from O. We consider two information regimes: in the known-d model, all robots are given d but not the direction of x; in the unknown-d model, neither the radius nor the direction is supplied. Both models use the same unit-speed and visibility assumptions. Robots share a coordinate frame and a clock, or agree on directions and a common start time before departure. For n = 2, we√show that the √ first regime is exactly solvable, and that the second has optimal competitive ratio at least 3 + π/6 + 17/4, strictly larger than the first, and at most 8.928516954 . . .. For unknown d we analyze an antipodal logarithmic-spiral search method whose competitive cost can be calculated in physical time. For n ≥ 3 robots, the competitive ratio of finding the target is exactly sec(π/n) regardless of whether or not d is known to the robots. ∗

Research supported in part by Natural Sciences and Engineering Research Council of Canada.

1

1.1

Notation and Terminology

We introduce the necessary notation for n = 2 robots and make the necessary adjustments for n ≥ 3 robots in Section 4. Let O = (0, 0), and let a, b : [0, ∞) → R2 be the positions of robots A, B at physical time t. The two robots start at the same time at O: a(0) = b(0) = O,

∥a(t) − a(s)∥ ≤ |t − s|,

∥b(t) − b(s)∥ ≤ |t − s|,

(1)

for s, t ≥ 0. Thus each robot has maximal speed one. Their visibility set at time t is the instantaneous closed line segment S(t) = [a(t), b(t)] = {(1 − λ)a(t) + λb(t) : 0 ≤ λ ≤ 1}. A deterministic search algorithm A specifies a pair of robot trajectories aA , bA satisfying (1); before the first detection they cannot receive any target-dependent information. Let A be the class of all such algorithms. The letter A in CRA names an algorithm; the two robot positions of that algorithm are aA , bA . The class A consists of strategies that do not know d and includes arbitrary admissible trajectories. After fixing an algorithm, we abbreviate its robot positions aA , bA to a, b when no confusion is possible. For a stationary target x ∈ R2 \ {O}, write d = d(x) := ∥x − O∥ = ∥x∥ > 0. Its first detection time and the two competitive ratios are defined by TA (x) , CR∗ := inf CRA = CR∗unknown d . A∈A x̸=O d(x)

TA (x) := inf{t ≥ 0 : x ∈ [aA (t), bA (t)]}, CRA := sup

(2)

Here and everywhere below, the denominator is the offline optimum d. Since the target location is unknown, TA (x) can be infinite for an unsuccessful algorithm. If the exact target x were given to the robots, one robot could move straight from O to x in time d, while the other stayed at O. Conversely, for any target point x ∈ [aA (t), bA (t)] there is a λ ∈ [0, 1] such that d = ∥x∥ = ∥(1 − λ)aA (t) + λbA (t)∥ ≤ (1 − λ)∥aA (t)∥ + λ∥bA (t)∥ ≤ t. Thus no algorithm can discover x sooner than d; the offline optimal detection time equals exactly d. In Section 2, an algorithm may depend on the supplied d; Section 3 considers the class A above. In either model, the offline optimum remains exactly d. If TA (x) < ∞, the infimum in (2) is a minimum. Indeed write hx (t) := min0≤λ≤1 ∥x − (1 − λ)aA (t) − λbA (t)∥. For the same λ at times t, s, the two corresponding segment points are at distance at most |t − s| by the 1-Lipschitz motion constraints. Minimizing over λ in both directions shows |hx (t) − hx (s)| ≤ |t − s|. Thus hx is continuous, and the detection-time set {t ≥ 0 : hx (t) = 0} is closed. Exact, scale-invariant spiral paths make infinitely many turns as t ↓ 0. They are nonetheless welldefined, continuous, 1-Lipschitz trajectories starting at O at t = 0. If a finite initial number of maneuvers is required, one may instead impose a known positive lower bound on d and modify the initialization; exact multiplicative ratios then require a separate initialization analysis. The algorithms below are continuous-time trajectory specifications in that for every physical time t > 0 the displayed formula prescribes each robot’s location, and a continuous sensor reports the first instant at which the unknown target belongs to the indicated segment. We denote this sensor by Hit([P, Q]); the sensor returns true exactly if the unknown target lies in [P, Q], without revealing the target’s position. In every algorithm the robots start at O. Algorithm 1 uses the specified distance d as input; Algorithm 2 does not. The spiral expressions involving log t apply only for t > 0.

1.2

Literature Review

Competitive geometric search has its origins in search games, including Gal’s minimax framework for linear and planar searching [2, 3, 5, 6]. Note that single robot search in the plane can be thought of as segment visibility whereby one of the searchers stays fixed at the origin. For such a single unit-speed searcher with origin-to-observer radial visibility, logarithmic-spiral search is known to have an optimal ratio of approximately 17.28935 . . .. Gal’s work supplies the classical spiral construction, whereas Langetepe [7] proves optimality among unrestricted single-observer strategies. That visibility rule is different from the present problem: our observed segment joins two moving robots, and a target may be discovered at an interior chord point. 2

A particularly useful comparison is shoreline search, in which mobile robots attempt to touch an unknown line in the plane and the performance denominator is the line’s distance from the origin [4, 10]. For two robots Acharjee, Georgiou, Kundu, and Srinivasan [1] proved a universal lower bound of 3. √ The subsequent work of Dobrev, Královič, and Pardubská [8] sharpened the two-robot lower bound to 1 + 3 + π/6 when the shoreline distance is known, matching the corresponding shoreline upper bound. Sections 2 and 4 explain how these shoreline results yield lower bounds for segment search. In Section 2, we make use of that theorem to prove a lower bound for our problem by reduction to the shoreline problem. A potentially useful method can be found in the recent preprint of Temerev [11]; its main theorem shows that for every d0 > 0, every deterministic path which searches all straight lines at distances d ≥ d0 has competitive ratio at least 12.5937096 . . ., but its approach does not directly improve our two-robot lower bound. Multi-agent spiral methods, including variants with different agent speeds, have also been studied [9]. The detection rules in this literature must be compared explicitly; trajectories designed for physical point encounters or for fixed-origin visibility cannot be transferred automatically to moving-chord visibility. In the unknown-radius model we study a pair of antipodal spirals, for which the joining chord is a full diameter. This family is not claimed optimal among arbitrary two-robot trajectories when d is unknown.

1.3

Results and Organization

√ For two robots, we first determine the exact deterministic optimum for a known target √ radius, 1+ 3+π/6 ≈ √ 3.255649583. For unknown d, we prove the stronger unconditional lower bound 3 + π/6 + 17/4 ≈ √ 3.286425990. The resulting separation from the known-radius optimum is at least ( 17−4)/4 ≈ 0.030776406. The best upper bound developed here for the latter model is achieved by antipodal logarithmic spirals. Model n = 2: Known d n = 2: Unknown d n ≥ 3: Known/Unknown d

Established Competitive Ratio √ π CR∗known d = 1 + 3 + 6 √ 17 √ π ∗ + 3 + ≤ CRunknown d ≤ 8.928516954 . . . 4 6 sec(π/n)

Section 2 proves the known-radius tight result, with algorithmic pseudocode, feasibility, coverage, and the shoreline reduction. Section 3 analyzes the unknown-radius antipodal spiral algorithm and proves the explicit three-circle lower bound. Section 4 extends the results to n ≥ 3 searchers. Section 5 summarizes the results and proposes some open questions.

2

Two Robots: Known Distance of Target from the Origin

Here we analyze the competitive ratio of ray search when both robots are informed of the target radius d > 0 but not its angular position. The value d may be used when choosing the trajectory pair; the target is discovered when it belongs to their current joining segment. We establish matching upper and lower bounds for all deterministic admissible strategies, not just the symmetric algorithm used for the upper bound. Let Ad denote the class of admissible algorithms allowed to use the known parameter d. For the circle Sd = {p ∈ R2 : ∥p∥ = d} and each A ∈ Ad , define TA (p) , CR∗known d := inf CRA,d . A∈Ad d p∈Sd √ The offline optimum for each p ∈ Sd is d (Section 1). For convenience set C0 = 1 + 3 + π/6. TA (p) := inf{t ≥ 0 : p ∈ [a(t), b(t)]}, CRA,d := sup

Theorem 2.1 (Optimal deterministic search with known target radius). For every specified d > 0, √ π CR∗known d = 1 + 3 + . 6 3

(3)

Algorithm 1 attains this ratio, with exact worst-case discovery time C0 d. The matching lower bound holds for all deterministic admissible trajectories, without symmetry, monotonicity, or boundary-following assumptions. We prove the upper bound in Subsection 2.1. For the lower bound in Subsection 2.2, we invoke the known-distance shoreline theorem of Dobrev, Královič, and Pardubská [8], and give a detailed reduction from segment discovery to shoreline search.

2.1

Upper Bound

Define the waypoints   d A± = ± √ , d , B± = 3

√

3d d ± , 2 2

! , C± = (±d, 0), D± = (±d, −d).

Each robot follows the corresponding trajectory straight segment OA± , the tangent segment A± B± , the short circular arc B± C± , and finally the vertical segment C± D± . Both robots execute the phases simultaneously at unit speed and the operator Hit([a(t), b(t)]) detects whether or not the target lies in the segment [a(t), b(t)]. Algorithm 1 Optimal segment search for a target at known radius d Require: Known target radius d > 0; continuous segment-detection sensor. 1: Start both robots at O and assign signs σ ∈ {−1, +1}. 2: Throughout all phases, monitor Hit([a(t), b(t)]); on the first hit, report discovery and stop both robots. √ 3: In parallel, robot σ travels straight to Aσ = (σd/ 3, d) at unit speed. √ 4: In parallel, robot σ travels straight to Bσ = (σ 3d/2, d/2) at unit speed. 5: In parallel, robot σ follows the circle towards Cσ = (σd, 0) at unit speed. 6: In parallel, robot σ travels vertically to Dσ = (σd, −d) at unit speed. 7: Every possible target has been detected by this time. Figure 1 illustrates the complete construction. y A−

A+

B−

C−

D−

B+

O

C+

P↓

x

D+

Figure 1: Optimal known-radius discovery, drawn for d = 1. After straight deployment (blue) and tangent motion (orange), the robots follow only the short arcs to the equator (teal), then move vertically downwards (purple). The dashed horizontal segment illustrates the final scan of the lower semicircle. The bottom point P↓ = (0, −d) is the worst-case target.

4

2.1.1

Physical-time trajectories and feasibility

Define the transition times √ √ π 2d 3+ d, t4 = C0 d. t1 = √ , t2 = 3d, t3 = 6 3 For σ ∈ {−1, +1}, the prescribed position of robot σ at time t is given by  √  0 ≤ t ≤ t1 , (σt/2, 3t/2),     σ d/√3 + (t − t )/2
, d − √3(t − t )/2
, t1 ≤ t ≤ t2 , 1 1 pσ (t) = (σd sin θ(t), d cos θ(t)), θ(t) = π/3 + (t − t2 )/d, t2 ≤ t ≤ t3 ,    (σd, −(t − t )), t3 ≤ t ≤ t4 . 3

(4)

Set a(t) = p+ (t) and b(t) = p− (t). After t4 , keep the prescribed no-detection positions fixed. These formulas are interrupted at discovery. Lemma 2.2 (Admissibility). The trajectories in (4) start at O simultaneously, are continuous, and 1-Lipschitz. Proof. The formulas give O at t = 0 and agreeq at the successive waypoints Aσ , Bσ , Cσ , and Dσ . The velocity √ norms in the first two phases are respectively (1/2)2 + ( 3/2)2 = 1 and the same quantity. In the circular phase, θ′ (t) = 1/d, so p′σ (t) = (σ cos θ(t), − sin θ(t)) and ∥p′σ (t)∥ = 1. The final velocity is (0, −1). Therefore each path is continuous and piecewise continuously differentiable with speed at most one. Integration over any time interval, splitting at transition times if necessary, gives ∥pσ (t) − pσ (s)∥ ≤ |t − s|. 2.1.2

Coverage and exact worst-case discovery time

Proposition 2.3. Algorithm 1 discovers √ every point of the circle Sd by time C0 d, and its exact worst-case discovery time is C0 d, where C0 = 1 + 3 + π/6. Proof. We verify coverage of three portions of Sd in order. Any detection during the initial deployment only improves the search time. √ Upper cap, d/2 ≤ y ≤ d. During the tangent phase, put u = t − t1 ∈ [0, d/ 3]. The endpoints are (±X(u), Y (u)), where √ d u 3u X(u) = √ + , Y (u) = d − . 2 3 2 Their squared distance from the origin satisfies   d 2 X(u)2 + Y (u)2 = d2 + u − √ ≥ d2 . 3 p Since X(u) ≥ 0,p this implies X(u) ≥ d2 − Y (u)2 . Thus the horizontal connecting segment contains both circle points (± d2 − Y (u)2 , Y (u)). The height Y (u) decreases continuously from d to d/2, covering the entire upper cap by t2 . Remaining upper semicircle, 0 ≤ y ≤ d/2. During the circular phase θ increases from π/3 to π/2. The endpoints themselves visit every point of the two corresponding arcs. An endpoint is part of the closed visibility segment. Consequently, by t3 the entire upper semicircle has been discovered. Lower semicircle, −d ≤ y ≤ 0. During the final phase write s = t − t3 ∈ [0, d]. The visibility segment is [a(t), b(t)] = {(z, −s) : −d ≤ z ≤ d}.

5

(5)

√ It contains both points (± d2 − s2 , −s) on the target circle. As s runs from zero to d, this covers the lower semicircle. The coverage argument, together with Lemma 2.2, proves supp∈Sd TA (p) ≤ t4 = C0 d for Algorithm 1. For equality, place the target at P↓ = (0, −d). In the first three phases both endpoints have nonnegative height, and so does every point of their segment. In the last phase the segment has height −s > −d whenever s < d. Therefore P↓ is not detected before t4 and is detected at t4 . This proves the exact worst-case assertion.

2.2

Lower Bound

The shoreline problem has the same start and speed constraints, but the “hidden object” is an infinite line at known distance d from O. The line is found when either robot physically touches it. Observe that every such line can be written uniquely as ℓu,d = {z ∈ R2 : u · z = d}, ∥u∥ = 1, where u points from O towards the nearest point on the line. Indeed, the line passes through p = du. For any other point z on it, the displacement z − p lies along the line and is therefore perpendicular to u, i.e., u · (z − p) = 0. Substituting p = du gives u · z = d(u · u) = d, because ∥u∥ = 1. Fix a deterministic search algorithm, and let a, b be the trajectories it prescribes under the hypothetical assumption that no target is ever detected. Define the shoreline hitting time Ha,b (u; d) = inf{t ≥ 0 : a(t) ∈ ℓu,d or b(t) ∈ ℓu,d }.

(6)

In the sequel, we make use of the following two-agent known-distance lower bound proved by Dobrev, Královič, and Pardubská [8]. Theorem 2.4 ([8]). For any two admissible deterministic robot trajectories starting at O, even when they are chosen with knowledge of d, √ Ha,b (u; d) π sup ≥1+ 3+ . d 6 ∥u∥=1 We invoke their theorem for unrestricted trajectories; in particular, we do not assume that each robot searches a prescribed semicircle. The following reduction is proved below. For fixed paths a, b, write Ta,b (x) := inf{t ≥ 0 : x ∈ [a(t), b(t)]}. If these are the paths of algorithm A, then Ta,b (x) = TA (x). Lemma 2.5 (A tangent line is reached no later than its tangency target). For every admissible trajectory pair a, b, every d > 0, and every unit vector u ∈ R2 , Ha,b (u; d) ≤ Ta,b (du).

(7)

Proof. Let A denote the algorithm generating a, b. If TA (du) = ∞, then the inequality holds. Otherwise put T = TA (du). Continuity of the moving segment ensures that the first detection is attained, as justified in Section 1. Hence, for some λ ∈ [0, 1], du = (1 − λ)a(T ) + λb(T ). Taking the scalar product with u and using ∥u∥ = 1 yields d = (1 − λ)u · a(T ) + λu · b(T ) ≤ max{u · a(T ), u · b(T )}. In the sequel, refer to Figure 2. Choose g ∈ {a, b} such that its projection at T is at least d. Its scalar projection s 7→ u · g(s) is continuous and starts at zero. Since d > 0, the intermediate value theorem gives s ∈ [0, T ] with u · g(s) = d. Thus g(s) ∈ ℓu,d and Ha,b (u; d) ≤ s ≤ T , proving the claim. Proof of Theorem 2.1. Fix any deterministic segment-search algorithm A that knows the target radius d. Let a, b be the trajectories prescribed by A under the hypothetical assumption that no target is ever detected. These trajectories are independent of the target’s unknown direction.

6

ℓu,d : u · z = d

a(T ) u O

p = du

b(T )

Figure 2: Reduction to shoreline search, shown with d = 1 and u = (1, 0). If the current segment contains p = du, at least one endpoint has projection at least d along u. Since that endpoint started at O, it must have touched the tangent line ℓu,d at or before this detection time. The displayed configuration is illustrative, not part of the upper-bound algorithm. Construct a shoreline-search algorithm by having the robots follow a, b until one of them reaches the hidden line. This is a valid known-distance shoreline-search algorithm: its motion schedule uses the given distance d, but does not use the unknown location or orientation of the line. Lemma 2.5 holds for every direction u, so √ Ha,b (u; d) TA (du) π ≥ sup ≥1+ 3+ , d d 6 ∥u∥=1 ∥u∥=1

CRA,d = sup

where the last inequality is Theorem 2.4. Taking the infimum over all A gives the desired universal lower bound. Proposition 2.3 gives an admissible algorithm attaining the same value, which proves equality.

3

Two Robots: Unknown Distance of Target from the Origin

We now require the robots to search without knowing either the target’s distance d or its angular direction.

3.1

Upper Bound

Unlike the preceding four-phase algorithm, a valid strategy here must prescribe its trajectories without using d. We study a scale-invariant logarithmic-spiral construction: the robots follow two antipodal spirals with the visibility segment passing through O (see Figure 3). The construction uses physical time and works for every d > 0. Choose λ > 0, a fixed reference time t∗ > 0, and a phase θ∗ ∈ R. These choices are independent of the target. Put v=√

λ , 1 + λ2

θ(t) = θ∗ +

1 log(t/t∗ ), λ

r(t) = vt

(t > 0).

(8)

The prescribed paths are a(0) = b(0) = O,

a(t) = r(t)(cos θ(t), sin θ(t)),

b(t) = −a(t)

(t > 0).

(9)

The reference time merely fixes a normalization; one may take t∗ = 1 and θ∗ = 0. Eliminating time gives the logarithmic spiral r = vt∗ eλ(θ−θ∗ ) . The angle has no finite limit at zero, but the positions converge to O. No positive initial radius or limiting initialization is used.

7

A x O

B

Figure 3: Two different rotated logarithmic spirals in Algorithm 2, one followed by each robot at speed one. The chord contains the origin O at every time and detects any target on the current diameter. Algorithm 2 Antipodal logarithmic-spiral search Require: λ > √ 0; fixed t∗ > 0 and θ∗ ∈ R; continuous segment-detection sensor 1: Set v ← λ/ 1 + λ2 2: Start both robots at a(0) = b(0) = O at time 0 3: while no target has been detected do 4: For physical time t > 0, set r(t) = vt and θ(t) = θ∗ + λ−1 log(t/t∗ ) 5: Move simultaneously along a(t) = r(t)(cos θ(t), sin θ(t)) and b(t) = −a(t) 6: Continuously monitor Hit([a(t), b(t)]) 7: end while 8: Announce detection and stop both robots The word antipodal means that the robots occupy opposite ends of a diameter at every positive physical time. The instantaneous visibility segment [−a(t), a(t)] is the union of two radial segments. Robot B does not traverse the same geometric spiral as robot A: its track is the half-turn rotation of A’s track. Theorem 3.1. For every λ > 0, Algorithm 2 is admissible in the start-at-origin model and has exact competitive ratio √ eπλ 1 + λ2 . (10) f (λ) = λ Its unique minimum over this family occurs at the positive solution λ∗ of πλ∗ (1 + (λ∗ )2 ) = 1, where λ∗ ≈ 0.293124142982 and f (λ∗ ) ≈ 8.928516954107. Proof. For a logarithmic spiral, radial distance grows with the angle: r = aeλθ . Hence, qexponentially √
dr ds dr 2 in polar coordinates is dθ = r2 + dθ = r 1 + λ2 . Since the robot moves at dθ = λr. The arc length √ dr dr 2 √1 √1 √ λ unit speed, 1 = ds dt = r 1 + λ θ̇, hence θ̇ = r 1+λ2 and ṙ = dt = dθ θ̇ = λr · r 1+λ2 = 1+λ2 . Thus the λ radial speed (i.e., the rate at which its distance from the origin increases) is constant: v = √1+λ . 2 The two robots are antipodal, so the detecting segment is the diameter [a(t), b(t)], whose supporting line is the ray of angle θ(t) modulo π. Therefore a target at polar coordinates (d, ϕ) is detected exactly when θ(t) ≡ ϕ (mod π) and d ≤ r(t). For a fixed target direction ϕ, the successive detection angles are θk = ϕ + kπ, k ∈ Z. The corresponding radii are

Rk = r0 eλ(ϕ−θ0 +kπ) = R0 q k ,

q = eλπ , R

R0 = eλ(ϕ−θ0 ) .

Thus consecutive possible detection radii differ by the factor Rk+1 = eλπ = q. k Let d be the unknown target distance, and let k be the first index with Rk ≥ d. Then the algorithm 0 detects the target at time tk = Rkv−r0 . Since Rk−1 < d, we have Rk = qRk−1 < qd. Therefore tk ≤ qd−r = v 8

q q r0 v d − v . Ignoring the additive initial-radius term, or taking r0 → 0, the algorithm’s time is at most v d.

The offline optimum is at least d, because the target is at distance d from the origin and the searcher has unit speed. Hence √ qd/v q eλπ 1 + λ2 CR(λ) ≤ = = . d v λ Conversely, fix ε > 0 and choose a target distance d = (1 + ε)Rk−1 . Then the target is not detected at q radius Rk−1 , and it is first detected at radius Rk = qRk−1 = 1+ε d. The algorithm’s time divided by the offline time is therefore Rk /v q q = −→ (ε → 0). d v(1 + ε) v λπ

√

1+λ2 . λ √ eλπ 1+λ2 It remains to choose λ > 0 optimally. Define f (λ) := . Then ln f (λ) = λπ + 12 ln(1 + λ2 ) − ln λ, λ d λ λ 1 1 2 so dλ ln f (λ) = π + 1+λ 2 − λ . Setting this equal to zero gives π + 1+λ2 − λ = 0, or equivalently πλ(1+λ ) = 1. ⋆ The unique positive solution is λ ≈ 0.293124142982 . . . . At this value, the competitive ratio is

Thus, the competitive ratio can be expressed as CR(λ) = e

⋆

eλ π

p 1 + (λ⋆ )2 ≈ 8.928516954107 . . . , λ⋆

which completes the proof of Theorem 3.1.

3.2

Lower Bound

Recall that the two robots start simultaneously at O = (0, 0) and follow paths a, b : [0, ∞) → R2 satisfying a(0) = b(0) = O,

∥a(t) − a(s)∥ ≤ |t − s|,

∥b(t) − b(s)∥ ≤ |t − s|

(s, t ≥ 0);

(11)

they have maximum speed of one and their paths are 1-Lipschitz. For a target x ̸= O, define Ta,b (x) := inf{t ≥ 0 : x ∈ [a(t), b(t)]},

inf ∅ := +∞.

(12)

The offline discovery time is ∥x∥: one robot can go straight to x, and no connecting segment can contain a point farther than t from O at time t. Note that for fixed x, the set in (12) is closed. Indeed, if tn → t and x = (1 − λn )a(tn ) + λn b(tn ), take a subsequence with λn → λ ∈ [0, 1] and use continuity. Thus Ta,b (x) < ∞ implies x ∈ [a(Ta,b (x)), b(Ta,b (x))]. For a nonempty set of possible targets F ⊆ R2 \ {O}, write Ta,b (x) , C(F ) := inf CRF (a, b). (a,b) satisfying (11) x∈F ∥x∥

CRF (a, b) := sup

(13)

The paths in (13) may depend on the candidate set F , but not on the hidden target’s identity. They represent the schedule prescribed by a deterministic algorithm under the hypothetical assumption that no target is ever detected. Actual execution can stop at the first detection. Let Sr := {x ∈ R2 : ∥x∥ = r}

(r > 0), CR∗unknown d := C(R2 \ {O}).

(14)

In the sequel, we invoke Theorem 2.1, namely C(Sr ) = CR∗known d = C0 := 1 +

√

3+

π ≈ 3.255649583 < 4 6

(r > 0).

(15)

As previously shown, if ru ∈ [a(t), b(t)], where ∥u∥ = 1, then max{u · a(t), u · b(t)} ≥ r; continuity implies that one robot has already touched the tangent line u · z = r. 9

Two facts will be used repeatedly: scaling space and time preserves the optimal ratio, and restricting the target set cannot increase it. Specifically, C(λF ) = C(F ), aλ (t) = λa(t/λ), bλ (t) = λb(t/λ), F ⊆G

=⇒

(λ > 0).

C(F ) ≤ C(G).

(16) (17)

Fix the target set E := S1/8 ∪ S1/4 ∪ S1 , CE := C(E).

(18)

The robots may know all three radii 1/8, 1/4, 1, but are not told which circle contains the target. Now we state the main result which is based on the three-circle construction and differentiates between search with “known” and “unknown” d. Theorem 3.2. Consider the target set E defined in (18). In the deterministic model (11)–(13), √ 17 ∗ C0 + δ0 ≤ CE ≤ CRunknown d , δ0 := − 1 = 0.0307764064 . . . . 4

(19)

Consequently, the constant c :=

CE − C 0 2

(20)

is finite and strictly positive, and satisfies CR∗known d +c < CE ≤ CR∗unknown d .

(21)

In particular,

√ π 17 3+ + = 3.2864259895 . . . . 6 4 The number c is independent of the algorithm and of the target, and satisfies √ 17 − 4 ≤ c ≤ 0.9875586419 . . . < 1. 8 CR∗unknown d ≥

√

(22)

(23)

The rest of this subsection develops the proof of Theorem 3.2 and supplementary structural results. We first explain the qualitative obstruction: equality on the outer circle forces one straight initial trajectory (Lemma 3.3), and four perpendicular targets exclude equality on E (Lemmas 3.4 and 3.5). The exactequality and compactness arguments (Lemmas 3.3, 3.5, and 3.6) provide supplementary explanations. The quantitative lower bound itself needs only the four-point lemma and the narrow-strip lemma. We then quantify the initial-path constraint using a narrow strip, proving the stated explicit gap (Lemma 3.7). Lemma 3.3. Suppose an admissible pair a, b satisfies Ta,b (x) ≤ C0

for every x ∈ S1 .

(24)

Then, after possibly exchanging the robot names, there is a unit vector u such that a(t) = tu

(0 ≤ t ≤ 1).

(25)

Proof. Define the first time either endpoint reaches the unit circle by τ := inf{t ≥ 0 : max(∥a(t)∥, ∥b(t)∥) = 1}.

(26)

This time exists and is finite: detection of any unit-circle point requires at least one endpoint to have norm at least 1, and continuity forces a preceding endpoint contact with S1 . The speed constraints imply τ ≥ 1. At time τ , both norms are at most 1, and one is exactly 1. 10

v S1 S1/4 2rv rv

a(t) = tu

−rv −2rv

u = a(1)

S1/8 r = 1/8 v⊥u

Figure 4: The candidate set E is fixed before the algorithm is chosen. If an algorithm had ratio C0 on E, its performance on S1 would force one robot to follow the blue straight segment during 0 ≤ t ≤ 1. The perpendicular direction v may then be chosen from that trajectory. All four red targets belong to the already fixed set E, and their deadlines precede time 1. Before τ , neither robot has norm 1, and for every λ ∈ [0, 1], ∥(1 − λ)a(t) + λb(t)∥ ≤ max{∥a(t)∥, ∥b(t)∥} < 1

(t < τ ).

Thus no point of S1 is detected before τ . We claim that τ = 1. Indeed, suppose on the contrary that τ > 1. Replace the initial motions by straight paths to the endpoint positions at time τ , and then replay the original schedule: ( ( t a(τ ), 0 ≤ t ≤ 1, 0 ≤ t ≤ 1, eb(t) = t b(τ ), e a(t) = (27) a(t + τ − 1), t ≥ 1, b(t + τ − 1), t ≥ 1. Both paths in (27) satisfy (11): their initial speeds are at most 1, the later portions are time translates of admissible paths, and the positions agree at the join t = 1. Every original unit-circle detection occurs at some s ≥ τ and is reproduced at time 1 + s − τ . By (24), the new pair therefore detects every point of S1 by 1 + C0 − τ < C0 .

(28)

This contradicts C(S1 ) = C0 from (15). Hence τ = 1, which proves the claim. Relabel so that a(1) = u with ∥u∥ = 1. For 0 ≤ t ≤ 1, the 1-Lipschitz property gives ∥a(t)∥ ≤ t, ∥u − a(t)∥ = ∥a(1) − a(t)∥ ≤ 1 − t. Consequently, 1 = ∥u∥ ≤ ∥a(t)∥ + ∥u − a(t)∥ ≤ t + (1 − t) = 1, and all inequalities are equalities. For 0 < t < 1, equality in the Euclidean triangle inequality places a(t) on the segment [O, u], at distance exactly t from O. Thus a(t) = tu; the endpoint cases follow as well. Note that Lemma 3.3 does not assert uniqueness of the known-radius optimal algorithm. It only establishes one property shared by every pair satisfying (24). The compressed pair in (27) is used solely as a competitor for searching S1 ; it need not preserve detections on the smaller circles. 3.2.1

A four-point obstruction on a line

Next, in Lemma 3.4, we prove a general result concerning four-point line-search that will be used later. Lemma 3.4 (Four-point line-search bound). Let y : [0, ∞) → R be 1-Lipschitz with y(0) = 0. For z ∈ R, define σy (z) := inf{t ≥ 0 : y(t) = z}, (29) 11

again with inf ∅ = +∞. For every r > 0, σy (z) ≥ 4. z∈{−2r,−r,r,2r} |z| max

(30)

Proof. If any required level is never reached, (30) is immediate. Otherwise all four first hitting times are finite and attained. By replacing y by −y if necessary, assume that r is visited before −r. In the rest of the proof we refer to Figure 5. y(t)/r first +2r: time 8r

2 first +r

1 1 −1 −2

3

4

8

t/r

first −r first −2r

Figure 5: The shortest itinerary for the better outer-level order in Case 2 of Lemma 3.4. Its successive travel times are r, 2r, r, and 4r. The last target has distance 2r and cannot be reached before time 8r, giving ratio 4. Detours or waiting can only increase these times. Case 1: 2r is visited before −r. The path must first cover distance at least 2r from 0 to 2r, and then distance at least 3r to −r. Hence σy (−r) ≥ 2r + 3r = 5r, (31) which yields a ratio at least 5. Case 2: −r is visited before 2r. Reaching −r after first visiting r requires time at least r + 2r = 3r. Neither outer level has yet been visited: 2r has not been visited by the case assumption, and visiting −2r would require crossing −r first. Starting at −r, if the next outer level reached is −2r, visiting both outer levels requires at least r + 4r = 5r more time. If the next outer level is 2r, the required additional time is at least 3r + 4r = 7r. Therefore max{σy (−2r), σy (2r)} ≥ 3r + 5r = 8r. (32) The corresponding outer target has distance 2r, giving ratio at least 4. 3.2.2

Excluding equality on the three circles

Lemma 3.5 (No pair achieves C0 on E). There are no admissible paths a, b satisfying Ta,b (x) ≤ C0 ∥x∥

(x ∈ E).

(33)

Proof. Suppose, for a contradiction, that Inequality (33) holds. Because S1 ⊂ E, Lemma 3.3 applies. Relabel the robots so that a(t) = tu for 0 ≤ t ≤ 1, where ∥u∥ = 1. Choose a unit vector v perpendicular to u, and put r = 1/8. The four targets rv,

−rv,

2rv,

−2rv

(34)

all belong to E. Under (33), their detection deadlines are at most 2rC0 =

C0 < 1. 4

12

(35)

Thus every relevant detection occurs while v · a(t) = 0. Define the scalar projection y(t) := v · b(t) (0 ≤ t ≤ 1).

(36)

This function starts at zero and is 1-Lipschitz, since |v · (b(t) − b(s))| ≤ ∥b(t) − b(s)∥ ≤ |t − s|. Extend it constantly for t ≥ 1, preserving that property. Let z ∈ {±r, ±2r}, and let tz = Ta,b (zv) < 1. At this detection time there is a λ ∈ [0, 1] with zv = (1 − λ)a(tz ) + λb(tz ),

z = λy(tz ).

(37)

Here λ > 0, because z = ̸ 0. If z > 0, (37) gives y(tz ) ≥ z; if z < 0, it gives y(tz ) ≤ z. By continuity from y(0) = 0, the scalar path has reached level z by time tz . Therefore σy (z) ≤ Ta,b (zv) ≤ C0 |z|

(z ∈ {±r, ±2r}).

(38)

Equation (38) contradicts Lemma 3.4, because C0 < 4. The direction v in this proof depends on the proposed trajectories, which is legitimate for a worst-case lower bound. The candidate set E itself does not depend on them: it contains the four points (34) for every possible choice of v. See Figure 4. 3.2.3

Compactness and the uniform positive gap

Next we use compactness to show that the infimum is attained for the target sets. Lemma 3.6. Let F ⊆ R2 \ {O} be nonempty and bounded, and assume C(F ) < ∞. Then an admissible pair attains the infimum in (13): CRF (a, b) = C(F ). (39) Proof. Put cF = C(F ) and choose R > 0 with ∥x∥ ≤ R for all x ∈ F . By the definition of infimum, choose admissible pairs an , bn such that Tan ,bn (x) ≤ (cF + 1/n)∥x∥

(x ∈ F ).

(40)

Set H = (cF + 1)R. All deadlines in (40) lie in [0, H]. The paths on this interval are uniformly bounded, because ∥an (t)∥, ∥bn (t)∥ ≤ t ≤ H, and uniformly equicontinuous by (11). Apply Arzelà–Ascoli to the paired maps (an , bn ) : [0, H] → R4 . After passage to a subsequence, both paths converge uniformly to a, b. The limit paths start at O and retain the 1-Lipschitz bounds. Fix any x ∈ F . For each index of this subsequence choose a detection time sn and segment parameter λn with 0 ≤ sn ≤ (cF + 1/n)∥x∥, 0 ≤ λn ≤ 1, x = (1 − λn )an (sn ) + λn bn (sn ). (41) Such witnesses exist by attainment of finite detection times. Compactness of [0, H] × [0, 1] gives a further subsequence on which sn → s and λn → λ. Then s ≤ cF ∥x∥. Moreover, ∥an (sn ) − a(s)∥ ≤ sup ∥an (t) − a(t)∥ + |sn − s| −→ 0, t∈[0,H]

and the same holds for bn . Passing to the limit in (41) gives x = (1 − λ)a(s) + λb(s),

s ≤ cF ∥x∥.

(42)

The limiting paths a, b were fixed before x was chosen. Only the subsequence of witnesses may depend on x; thus (42) holds for every x ∈ F for this same pair. There is no need to select one subsequence of witnesses simultaneously for an uncountable set of targets. Extend both limiting paths constantly after time H. This preserves (11) and every detection in (42). Their ratio on F is at most cF , and cannot be smaller than its infimum C(F ) = cF . This proves (39). 13

3.2.4

Quantitative initial-path estimate

Lemma 3.7 (A narrow strip before first unit-circle contact). Suppose an admissible pair discovers every point of S1 by time C. Let τ be the first time either endpoint reaches S1 . After relabeling, write a(τ ) = u with ∥u∥ = 1. Then 1 ≤ τ ≤ 1 + C − C0 . (43) For every unit vector v ⊥ u and every 0 ≤ t ≤ τ , √ |v · a(t)| ≤

τ2 − 1 . 2

(44)

Proof. No unit-circle target is detected before τ . The compressed paths in (27) therefore discover all of S1 by time 1 + C − τ . The known-radius lower bound implies C0 ≤ 1 + C − τ , thus proving (43). Write a(t) = xu + yv. Unit speed gives p p x2 + y 2 + (1 − x)2 + y 2 = ∥a(t)∥ + ∥u − a(t)∥ ≤ t + (τ − t) = τ. p Applying the triangle inequality to (x, y) and (1 − x, y) yields 1 + 4y 2 ≤ τ , which proves (44). Finally, we are in a position to prove the main theorem 3.2. √ √ 0 Proof of Theorem 3.2. Recall the parameters δ0 = 417 − 1, c = CE −C , C0 = 1 + 3 + π6 in the statement 2 of the theorem. Suppose, for a contradiction, that a pair has ratio C < C0 + δ0 on E; necessarily C ≥ C0 . Its unit-circle targets are discovered by time C, so Lemma 3.7 supplies an endpoint a(τ ) = u and gives √ 17 1 ≤ τ ≤ 1 + C − C0 < 1 + δ0 = . 4

Choose a unit vector v ⊥ u and put r = 1/8. For 0 ≤ t ≤ τ , √ τ2 − 1 1 |v · a(t)| ≤ < = r. 2 8

(45)

All four targets zv, z ∈ {±r, ±2r}, belong to E and must be detected by time 2rC = C/4 < 1 ≤ τ , since C0 + δ0 < 4. At a detection time tz , take projections of the segment incidence: z = (1 − λ)v · a(tz ) + λv · b(tz ),

0 ≤ λ ≤ 1.

If z > 0, (45) implies v · a(tz ) < r ≤ z, so v · b(tz ) ≥ z. If z < 0, it implies v · a(tz ) > −r ≥ z, so v · b(tz ) ≤ z. The 1-Lipschitz scalar path yb (t) = v · b(t) starts at zero; continuity therefore gives σyb (z) ≤ tz ≤ C|z| for all four levels. Lemma 3.4 forces C ≥ 4, a contradiction. Thus no admissible pair can have ratio less than C0 +δ0 on E, and taking the infimum gives CE ≥ C0 +δ0 . Restriction gives CE ≤ CR∗unknown d . Proposition 3.8 below proves that CE < ∞ and establishes the upper bound in (23). Hence √ CE − C 0 δ0 17 − 4 c= ≥ = = 0.0153882032 . . . 2 2 8 Since C0 + c = (C0 + CE )/2 < CE , this concludes the proof of Theorem 3.2. Proposition 3.8 (Upper bound on the gap constant). The constant c in (20) is finite and satisfies c ≤ 0.9875586419309 . . . < 1.

14

Proof. Let L(r, R) =

q √ (R/ 3 − r)2 + (R + r)2 .

Search radii 1/8, 1/4, 1√in order using the known-radius algorithm. After finishing radius r at (±r, −r), move directly to (±R/ 3, R) and run the last three phases for radius R. Those phases cover all of SR , so the deployment phase need not be repeated. The completion times satisfy t1 = C0 /8,

√ t2 = t1 + L(1/8, 1/4) + (C0 − 2/ 3)/4, √ t3 = t2 + L(1/4, 1) + C0 − 2/ 3. Then CE ≤ max{8t1 , 4t2 , t3 } = 4t2 , yielding the exact upper bound c≤

1 C0 + 2L(1/8, 1/4) − √ = 0.9875586419309 . . . < 1. 4 3

(46)

For a simple conservative check of the maximum and the final inequality, use 3.2556 < C0 < 3.2557, 0.37549 < L(1/8, 1/4) < 0.37551, and 1.29215 < L(1/4, 1) < 1.29216, which imply 5.2306 < 4t2 < 5.2309 and t3 < 4.7010. This bounds the chosen c, not the full difference between the two optimal ratios. Corollary 3.9. For the positive constant c in (20), every deterministic universal search algorithm has some target x ∈ E such that Ta,b (x) > (C0 + c)∥x∥. (47) The same assertion holds with E replaced by S1 ∪ S2 ∪ S8 . Proof. For every pair, its supremum in (13) is at least CE > C0 + c. If every target satisfied the reverse non-strict inequality to (47), that supremum would be at most C0 + c, a contradiction. The final statement follows from (16), since 8E = S1 ∪ S2 ∪ S8 .

4

Search with n ≥ 3 Robots

This section extends instantaneous segment discovery to n ≥ 3 robots. We give the expanding regularpolygon algorithm, compute its exact competitive ratio, and prove optimality for arbitrary deterministic trajectories by reduction to shoreline search. We consider both known and unknown target distance.

4.1

Model and statement of the result

Robots 0, . . . , n − 1 start at O and have 1-Lipschitz trajectories pi : [0, ∞) → R2 . In the base model, every pairwise segment [pi (t), pj (t)] is visible. The polygon interior is not, in general, instantaneously visible. Our upper-bound algorithm needs only the segments joining cyclic neighbors i − 1, i, i + 1, with indices modulo n. We assume instantaneous notification of detection to stop the robots; the objective is discovery, and the Boolean sensor need not localize the target. For a deterministic algorithm B, let VB (t) be the union of its visible segments and put TB (x) = inf{t ≥ 0 : x ∈ VB (t)},

(n)

TB (x) , x̸=O ∥x∥

CRB = sup

(n)

CR∗n = inf CRB . B

(48)

The infimum is over admissible deterministic algorithms. The offline optimum is ∥x∥: no endpoint is farther than t at time t, so neither is any point on a visible segment, while sending two robots straight to x attains that time. The lower bound is proved for all-pairs visibility, while the upper bound uses only cyclic-neighbor segments, so the optimum is the same in both models. 15

For a supplied d > 0, define TBd (x) , Bd ∥x∥=d d

CR∗n,known d := inf sup

CR∗n,unknown d := CR∗n ,

(49)

where Bd may use d but not the target direction. Theorem 4.1. For every integer n ≥ 3, the algorithm An in Algorithm 3 does not use the target distance and has exact worst-case ratio (n)

CRAn = CR∗n,unknown d = CR∗n,known d = sec(π/n).

(50)

Optimality is among all admissible deterministic trajectories, with arbitrary turns and speeds at most one. The same optimum holds with only cyclic-neighbor visibility.

4.2

The algorithm and its geometric analysis

Define

2πi π , θi = , ui = (cos θi , sin θi ), pi (t) = tui . (51) n n At time t > 0 the robots form a regular n-gon of circumradius t. Its edges are the segments monitored by the algorithm, and its inradius is t cos β. β=

Algorithm 3 Expanding regular polygon An Require: n ≥ 3 robots at O, common clock and agreed directions; Ensure: Discovery of every stationary target x ̸= O, without knowing ∥x∥ 1: Assign robot i the vector ui = (cos(2πi/n), sin(2πi/n)), for 0 ≤ i < n 2: Assign robot i its two neighbors i − 1 and i + 1 modulo n 3: Start all robots simultaneously at time 0 4: while no target has been detected do 5: All robots move continuously and simultaneously: pi (t) = tui 6: Robot i continuously monitors [pi (t), pi−1 (t)] and [pi (t), pi+1 (t)] 7: end while 8: Detecting robots announce detection; all robots stop Lemma 4.2 (Exact discovery time). Let x have polar radius d > 0 and angle θ. Choose a sector [θi , θi+1 ] containing its direction, interpreting the last sector modulo 2π, and set φ = θ − (θi + β) in that sector. Then |φ| ≤ β and d cos φ TAn (x) = . (52) cos β Consequently the worst-case ratio is 1/ cos β, attained along every sector bisector. Proof. Let mi be the unit vector along the sector bisector and wi its counterclockwise perpendicular. In these coordinates the two endpoints are (t cos β, −t sin β) and (t cos β, t sin β), and x = (d cos φ, d sin φ) (see Figure 6). Membership in their segment requires d cos φ = t cos β, |d sin φ| ≤ t sin β. The first equality gives (52). At that time the second inequality follows from | tan φ| ≤ tan β, since 0 < β ≤ π/3 < π/2.

16

pi (t)

M

pi+1 (t)

x

|φ| d t

t 2β

O

O OM = t cos β

Expanding polygon (n = 5)

One sector at detection

Figure 6: Only the polygon edges are visible at a given instant. Their expansion sweeps the plane. In one sector, the projection of the target onto the sector bisector is d cos φ = t cos β. The worst direction is the bisector, where x = M and t/d = 1/ cos β. Thus detection occurs at the asserted time. For t > 0 each polygon edge lies in its corresponding closed angular sector. A target in the interior of the chosen sector cannot lie on any other edge. At a shared boundary direction, detection is at the common vertex at time d, also given by (52). This proves that there is no earlier edge detection. Every other pairwise segment lies inside the polygon, so it also cannot detect x before the expanding polygon boundary reaches x. Finally cos φ ≤ 1, with equality on the bisector, proving both the upper bound and its attainment. The trajectories have speed exactly one.

4.3

The unrestricted lower bound

We use the following shoreline-search bounds as external inputs; the reduction to segment discovery is proved below. Theorem 4.3 (Shoreline Search [1, 8]). For deterministic search for an unknown line by n unit-speed robots starting at O, with neither its direction nor its distance supplied, the competitive ratio is at least 1/ cos(π/n) for every n ≥ 3. For n ≥ 4 this is the result of [1]. For n = 3 the bound 2 is due to [8]; their three-robot bound holds even when the distance is known. For a fixed trajectory tuple p = (p0 , . . . , pn−1 ), define Hp (u; d) = inf{t ≥ 0 : some i satisfies u · pi (t) = d},

∥u∥ = 1,

d > 0.

(53)

This is the first endpoint contact with ℓu,d = {z : u · z = d}. Also let Tpall (x) be the discovery time when every pairwise segment is visible. Lemma 4.4 (Reduction for n endpoints). For every admissible tuple and every d > 0, ∥u∥ = 1, Hp (u; d) ≤ Tpall (du) ≤ TB (du),

(54)

where B uses these paths before discovery and monitors any subset of the pairwise segments. Proof. If du ∈ [pi (t), pj (t)], some λ ∈ [0, 1] satisfies d = (1 − λ)u · pi (t) + λu · pj (t). Thus at least one endpoint has projection at least d. Its projection starts at zero and is continuous, so it has reached d by time t. This proves Hp (u; d) ≤ t for every pairwise detection time; taking their infimum proves the first inequality, also when that infimum is infinite. The second follows because adding visible links cannot delay detection. In particular, no assertion that the visible set contains the whole convex hull is needed. 17

Lemma 4.5 (Known-radius lower bound for n ≥ 4). For n ≥ 4 robots, every deterministic segment-search algorithm, even one supplied with d > 0, has worst-case detection time at least d/ cos(π/n) on Sd . Proof. Fix d > 0, put β = π/n ≤ π/4, and let 0 < T < d/ cos β. For any n prescribed trajectories, choose an open angular cone of width 2β containing none of the robot positions at time T . Such a cone exists because the circular gaps between at most n nonzero endpoint directions sum to 2π; endpoints at O do not lie in an open cone. Let u bisect that cone, and consider the line ℓ = {z : u · z = d}. A contact point on ℓ outside the open cone has norm at least d/ cos β > T , so cannot be reached by time T . If a robot touches ℓ inside the cone, it must subsequently reach the cone boundary by T , because its final position is outside the interior. In coordinates along u and its perpendicular, write the contact as K = (d, y), where |y| < d tan β. The distance from K to the closer boundary ray is d sin β − |y| cos β; the orthogonal projection lies on that ray. The robot’s traveled length up to its exit is consequently at least p f (|y|) := d2 + y 2 + d sin β − |y| cos β. For 0 ≤ z ≤ d tan β, f ′ (z) = √

z d2 + z 2

− cos β ≤ sin β − cos β ≤ 0.

Hence f (|y|) ≥ f (d tan β) = d/ cos β > T , again impossible. No robot has touched this line by T . The endpoint-contact reduction then implies that the tangency target du has not been segment-detected by T . Since this holds for every T < d/ cos β, the worst-case time on Sd is at least d/ cos β, even for paths chosen using d. This argument adapts the geometric method in Section 2 of [1] to a fixed target radius. Proof of Theorem 4.1. Lemma 4.2 proves the upper bound. For the lower bound, fix any deterministic algorithm B for the unknown-distance segment problem. Let p be the paths it prescribes under the hypothetical assumption that no target is ever detected. This schedule is independent of the unknown target location. Construct a shoreline-search strategy by following exactly these paths until an endpoint reaches the actual hidden line. Do not stop or change the schedule at hypothetical point-target detections. This is an admissible shoreline strategy that uses neither the unknown line’s distance nor its direction. For every u, d, Lemma 4.4 compares the line-contact time with the segment discovery time for its tangency target du. Dividing by d and taking suprema yields Hp (u; d) TB (x) (n) ≤ sup = CRB . d x̸=O ∥x∥ ∥u∥=1, d>0 sup

(55)

Theorem 4.3 bounds the left side below by 1/ cos(π/n). Since B was arbitrary, the same bound holds after taking the infimum over segment-search algorithms. This matches the upper bound for unknown distance. For known distance and n = 3, apply the same tangent-line reduction at that fixed d to the known-distance shoreline bound 2 from [8]. For n ≥ 4, Lemma 4.5 gives the matching fixed-distance lower bound. The polygon algorithm does not use d, so supplies the upper bound in both cases. This proves (50). The lower bounds allow every pairwise segment to be visible, whereas the algorithm requires only cyclic-neighbor segments. This proves the assertion for both visibility conventions.

5

Conclusion

We have studied deterministic discovery by n ≥ 2 unit-speed robots in the plane, where a target is detected when it lies on an instantaneous segment joining a pair of robots. For n = 2, the knowledge of the target radius d leads to two fundamentally different outcomes. √ When d is known, the symmetric four-phase construction attains the exact optimum CR∗known d = 1 + 3 + π/6. When d is unknown, a search strategy must cover all radii without using d in its motion schedule. The three-circle obstruction and quantitative narrow-strip estimate give a strictly stronger lower bound than the known-radius optimum. We obtain 18

√

√

3 + π6 + 417 ≤ CR∗unknown d ≤ 8.928516954 . . . . For the latter model we analyzed a scale-invariant construction using two antipodal logarithmic spirals. It attains the displayed upper bound, which is optimal within that logarithmic-spiral family. For n ≥ 3, the expanding regular-polygon algorithm attains the exact optimum sec(π/n) for both known and unknown target radius, even using only cyclic-neighbor segments. Determining the unknown-radius optimum√for n = 2 robots remains the principal open problem. Subsection 3.2 gives an explicit separation of at least ( 17 −4)/4 between the two optimal ratios. Improving the choice of radii or strengthening the projection obstruction may yield larger quantitative lower bounds. A complementary direction is to improve upper bounds by allowing nonsymmetric, nonantipodal, or nonlogarithmic trajectories. Any matching lower-bound proof must account for the extra coverage provided by a segment with both endpoints moving; a result restricted to diameters or supporting-line contact would not by itself resolve the unrestricted problem.

Acknowledgements Many thanks to K. Georgiou for useful conversations in the initial stages of this research.

References [1] S. Acharjee, K. Georgiou, S. Kundu, and A. Srinivasan. “Lower Bounds for Shoreline Searching With 2 or More Robots.” OPODIS 2019, LIPIcs 153, article 26, published 2020. https://doi.org/10.4230/ LIPIcs.OPODIS.2019.26. [2] S. Alpern and S. Gal. “The Theory of Search Games and Rendezvous”, volume 55 of International Series in Operations Research and Management Science. Kluwer Academic Publishers, Boston, 2003. [3] R. A. Baeza-Yates, J. C. Culberson, and G. J. E. Rawlins. “Searching in the plane.” Information and Computation, 106(2):234–252, 1993. [4] S. R. Finch and L.-Y. Zhu. “Searching for a shoreline”, arXiv preprint math/0501123, 2005. [5] S. Gal. “Minimax solutions for linear search problems.” SIAM Journal on Applied Mathematics, 27:17–30, 1974. [6] S. Gal. Search Games, vol. 149 of Mathematics in Science and Engineering. Academic Press, New York, 1980. [7] E. Langetepe. “On the Optimality of Spiral Search.” Proceedings of the Twenty-First Annual ACM–SIAM Symposium on Discrete Algorithms, 2010, pp. 1–12. https://doi.org/10.1137/1. 9781611973075.1. [8] S. Dobrev, R. Královič, and D. Pardubská. “Improved Lower Bounds for Shoreline Search.” In A. W. Richa and C. Scheideler (eds.), Structural Information and Communication Complexity (SIROCCO 2020), Lecture Notes in Computer Science, vol. 12156, pp. 80–90. Springer, Cham, 2020. https: //doi.org/10.1007/978-3-030-54921-3_5. [9] K. Georgiou, C. Jones, and M. Madej. “Spirals and Beyond: Competitive Plane Search with Multi-Speed Agents.” arXiv:2508.10793, v3 (September 2026). https://arxiv.org/abs/2508.10793. [10] J. R. Isbell. “An optimal search pattern.” Naval Research Logistics Quarterly, 4(4):357–359, 1957. [11] A. Temerev. “A New Unconditional Lower Bound for Shoreline Search.” https://arxiv.org/pdf/ 2608.18362v1

19

Related documents

• 3D-printer system with object detection sensors — BeeHex, LLC (US11026433B2)#607562
• Anchor-Free Hidden-Target Seeking via Certified Self-Calibration under Correlated Odometry#1064449
• TRACE: Privacy-Preserving Next-Best-View Selection over Distributed 3D Gaussian-Splat Maps#1155757
• Algorithmic threshold for high-dimensional projection pursuit I: general theory#794206
• Algorithmic threshold for high-dimensional projection pursuit I: general theory#790187