pith. sign in

arxiv: 2604.02491 · v1 · submitted 2026-04-02 · 💻 cs.DS

Online Drone Coverage of Targets on a Line

Stefan Dobrev , Konstantinos Georgiou , Evangelos Kranakis , Danny Krizanc , Lata Narayanan , Jaroslav Opatrny , Denis Pankratov , Sunil Shende This is my paper

Pith reviewed 2026-05-13 20:26 UTC · model grok-4.3

classification 💻 cs.DS
keywords online algorithmscompetitive analysisdrone coverageangular viewline barriertrajectory optimizationtarget monitoring
0
0 comments X

The pith

An online drone algorithm covers line targets at 1.25 competitive ratio when the half-angle is 45 degrees, with a general lower bound of about 1.207.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies a drone equipped with a fixed half-angle camera view that must cover targets appearing one by one at arbitrary positions on a straight line. After each new target arrives, the drone immediately relocates to a position from which its view cone covers every target seen so far, and the goal is to keep the total distance traveled as small as possible in the worst case relative to an offline optimum that knows all targets in advance. Three online strategies are presented and analyzed for every angle between 0 and 90 degrees; the strongest, called FA, guarantees a ratio of 1.25 at exactly 45 degrees. A matching-style lower bound shows that no online strategy can guarantee a ratio better than (1 + square root of 2) over 2 for angles up to 45 degrees. These bounds give concrete limits on how much extra travel an online controller must accept when targets appear unpredictably.

Core claim

For a drone whose half-angle view is exactly π/4, the algorithm FA achieves a competitive ratio of 1.25 against an optimal offline solution. For any half-angle α in the interval [0, π/4], no online algorithm can guarantee a competitive ratio smaller than (1 + √2)/2 ≈ 1.207, and this lower bound is tightest at α = π/4.

What carries the argument

The algorithm FA, which at each step selects the drone position that covers the current set of targets while minimizing additional travel under the fixed half-angle constraint.

If this is right

  • For α = π/4 the algorithm FA never travels more than 25 percent farther than the optimal offline trajectory.
  • For every α in [0, π/4] every online algorithm must sometimes pay at least (1 + √2)/2 times the offline cost.
  • The other two presented algorithms achieve a competitive ratio of √2 for the same range of angles.
  • The competitive ratio remains bounded for all half-angles up to π/2, though the precise values differ outside the [0, π/4] interval.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same angular-covering model could be applied to online placement of mobile sensors in higher dimensions when targets are not forced to lie on a line.
  • The derived lower bound supplies a concrete benchmark that any future online strategy for this geometry must meet or exceed.
  • The movement cost analysis may transfer to related problems such as online guarding of a line segment with limited-range sensors.

Load-bearing premise

Targets appear in an arbitrary online sequence, forcing the drone to choose its next position immediately after each arrival so that the fixed angular view covers every target seen so far.

What would settle it

An explicit sequence of target positions on the line for which FA's total travel length exceeds 1.25 times the offline optimum when α equals π/4.

Figures

Figures reproduced from arXiv: 2604.02491 by Danny Krizanc, Denis Pankratov, Evangelos Kranakis, Jaroslav Opatrny, Konstantinos Georgiou, Lata Narayanan, Stefan Dobrev, Sunil Shende.

Figure 1
Figure 1. Figure 1: Two dimensional representation of our problem with [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: This plot depicts competitive ratios of algorithms studied in this paper as functions of [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The cost of the offline algorithm is segment from [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Algorithm Trajectories for α = π/4: OPT (in black), Straight-Up algorithm (in red), Greedy algorithm (in solid blue, which is equivalent in distance to the dotted blue trajectory), and the β-Hedge algorithm (in green). T h 1 T ′ α Xi X0 Xj U 1 [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The segments X0U and UT′ correspond to the path traveled by the Greedy algorithm when α > π/4. in this algorithm is very large. In the Greedy algorithm the angle of the displacement of the drone with respect to the y axis is either α or −α when α ≤ π/4 , and is either π/2−α or α−π/2 when α > π/4. Thus, when locations of the requests alternate between the left and right of (0, 0), the positions of the drone… view at source ↗
Figure 6
Figure 6. Figure 6: The path X0, U, T′ is traveled by the β-Hedge algorithm, while the length of the path traveled by the Greedy corresponds to |XjT|. height of U in the triangle X0XjU. Solving the two equations we get z = 2r tan β tan α+tan β . Substituting the value of z into the expression for |V T′ | we get |V T′ | = 2r tan β 2r sin β(tan α + tan β) · (1 + 2r tan β tan α + tan β ) = tan α + (1 + 2r) tan β (tan α + tan β) … view at source ↗
Figure 7
Figure 7. Figure 7: Performance parameters of the β-Hedge algorithm, as per Theorem 3. Lemma 5. For each α ∈ [0, π/2] and β ∈ [0, α], the competitive ratio of the β-Hedge algorithm equals max r∈[max{0,− cos(2α)},1] f1(α, β, r). Proof. For the competitive analysis, we need to describe the optimal offline cost, as a function α, r in simpler terms. For this, using simple trigonometric calculations, we simplify the statement of L… view at source ↗
Figure 8
Figure 8. Figure 8: plots the above expression for α ∈ [0, π/2] and for all β ∈ [0, α]. Below we show formally that the expression is non-positive, implying the claim of the lemma [PITH_FULL_IMAGE:figures/full_fig_p013_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The competitive ratio upper bound of Theorem [PITH_FULL_IMAGE:figures/full_fig_p015_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Supporting plots for the analysis of the critical points of [PITH_FULL_IMAGE:figures/full_fig_p017_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: The plot of d 2 dβ2 f1(α, β, r0) for all α ∈ [0, π/2] and β ∈ [0, α]. Numerical calculations show that the second derivative is at least 0.707355 (that is, it is bounded away from 0). function is convex (even when β ∈ [0, α]), and therefore f1(α, β, r0) is minimized either at the extreme values t(α), α or at any critical points of the function. In the first subcase α ≤ π/3, the function has no critical po… view at source ↗
Figure 12
Figure 12. Figure 12: Part (a) of this figure illustrates the situation described in the proof of Lemma [PITH_FULL_IMAGE:figures/full_fig_p020_12.png] view at source ↗
Figure 14
Figure 14. Figure 14: This figure shows ρ ∗ (on the left) and s ∗ (on the right) from Theorem 4 as functions of α. We can compute |Z2Z3| in another way using the formula for Zi = Ti + z(Ti + 1 − Tt). Then we obtain: |Z2Z3| = (1 − s 2 ) q (−1 + z + sz) 2 + (1 + (−1 + s)z) 2 cot2 (α). Substituting into (12) yields ρ(s − 1)s −4s + (1 + s) 2 sin2 (α) = (1 − s 2 ) q (−1 + z + sz) 2 + (1 + (−1 + s)z) 2 cot2 (α). Squaring the two exp… view at source ↗
read the original abstract

We study a problem of online targets coverage by a drone or a sensor that is equipped with a camera or an antenna of fixed half-angle of view $\alpha$. The targets to be monitored appear at arbitrary positions on a line barrier in an online manner. When a new target appears, the drone has to move to a location that covers the newly arrived target, as well as already existing targets. The objective is to design a coverage algorithm that optimizes the total length of the drone's trajectory. Our results are reported in terms of an algorithm's competitive ratio, i.e., the worst-case ratio (over all inputs) of its cost to that of an optimal offline algorithm. In terms of upper bounds, we present three online algorithms and prove bounds on their competitive ratios for every $\alpha \in [0, \pi/2]$. The best of them, called \FA is significantly better than the other two for $\pi/6 < \alpha < \pi/3$. In particular, for $\alpha=\pi/4$, its worst case, \FA has competitive ratio $1.25$, while the other two have competitive ratio $\sqrt{2}$. Finally, we prove a lower bound on the competitive ratio of online algorithms for a drone with half-angle $\alpha \in [0, \pi/4]$; this bound is a function of $\alpha$ that achieves its maximum value at $\alpha = \pi/4$ equal to $(1+\sqrt{2})/2 \approx 1.207$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript studies the online drone coverage problem on a line where targets arrive sequentially and the drone must immediately reposition to cover the new target plus all prior ones using a fixed half-angle view α. Three online algorithms are introduced and analyzed for competitive ratio against the optimal offline solution for all α ∈ [0, π/2]. The best algorithm FA is shown to achieve ratio 1.25 at α=π/4 (where the other two achieve √2), and a lower bound of (1+√2)/2 ≈1.207 is proved for α ∈ [0, π/4].

Significance. If the proofs hold, the work delivers the first competitive analysis for this geometric online covering task, with upper and lower bounds that are close enough to indicate near-optimality at the critical angle. The explicit adversarial constructions and algorithm descriptions strengthen the contribution and support potential follow-up work on higher-dimensional or dynamic variants.

major comments (1)
  1. [Proof of competitive ratio for FA at α=π/4] Proof of Theorem for FA at α=π/4 (case analysis on target orderings and coverage positions): the 1.25 ratio is obtained by charging movement costs against OPT via geometric constraints of the 45° cone. However, it is unclear whether the enumeration exhausts all sequences of three or more targets in which successive optimal covering locations force the online drone to incur repositioning distance that exceeds the 1.25 multiplier after the initial placements; the two-target lower-bound construction does not automatically certify that the upper-bound cases are complete.
minor comments (1)
  1. [Abstract] The abstract states the other two algorithms achieve √2 at α=π/4 but does not name them or give their ratios for the full range of α; adding these details would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful review and constructive comments on our manuscript. We address the major comment regarding the proof of the competitive ratio for algorithm FA at α=π/4 below.

read point-by-point responses

  1. Referee: [Proof of competitive ratio for FA at α=π/4] Proof of Theorem for FA at α=π/4 (case analysis on target orderings and coverage positions): the 1.25 ratio is obtained by charging movement costs against OPT via geometric constraints of the 45° cone. However, it is unclear whether the enumeration exhausts all sequences of three or more targets in which successive optimal covering locations force the online drone to incur repositioning distance that exceeds the 1.25 multiplier after the initial placements; the two-target lower-bound construction does not automatically certify that the upper-bound cases are complete.

    Authors: We appreciate the referee pointing out the need for clarity on the completeness of the case analysis. The proof of the 1.25 competitive ratio for FA at α=π/4 proceeds by exhaustive classification of all possible target arrival sequences, based on the relative positions of each new target with respect to the current coverage cone (defined by the 45° half-angle) and the positions chosen by the optimal offline solution. We analyze the incremental movement cost at each step for sequences of arbitrary length, charging any excess repositioning distance directly to the OPT trajectory using the geometric properties of the cone (specifically, the fact that any two points covered by a single cone position are at most a fixed distance apart). This charging argument holds inductively and does not rely on the two-target lower-bound construction, which is presented separately to establish the matching lower bound of (1+√2)/2. We believe the cases are complete as they cover all orderings that could force additional movements beyond the initial placements. However, to improve readability and address the concern explicitly, we will expand the case breakdown with additional subcases for three-or-more-target sequences in the revised version. revision: partial

Circularity Check

0 steps flagged

No significant circularity; competitive ratios derived from explicit case analysis and adversarial sequences

full rationale

The derivations consist of standard competitive analysis: upper bounds via case-by-case bounding of the online algorithm's trajectory length against an optimal offline solution (OPT), and lower bounds via explicit adversarial target sequences that force any online algorithm to incur at least a stated ratio. These steps are independent of fitted parameters, self-definitions, or load-bearing self-citations; the claimed ratios (1.25 upper, (1+√2)/2 lower at α=π/4) are obtained by direct geometric and ordering arguments on the line and coverage cones, not by renaming or constructionally equating inputs to outputs. The analysis is self-contained against external benchmarks (OPT and worst-case sequences).

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Analysis rests on the standard online adversarial model and basic geometric coverage definitions; no free parameters, invented entities, or non-standard axioms are introduced in the abstract.

axioms (2)
  • domain assumption Targets arrive in an arbitrary adversarial online sequence.
    The competitive ratio is defined with respect to worst-case inputs chosen by an adversary.
  • standard math Coverage occurs when the drone is at a point from which the fixed half-angle view includes the target.
    Geometric definition of the sensor model.

pith-pipeline@v0.9.0 · 5604 in / 1245 out tokens · 36612 ms · 2026-05-13T20:26:27.479884+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Angelis, and Konstantinos Oikonomou

    Konstantinos Bezas, Georgios Tsoumanis, Constantinos T. Angelis, and Konstantinos Oikonomou. Coverage path planning and point-of-interest detection using autonomous drone swarms. Sensors, 22(19), 2022

    work page 2022

  2. [2]

    Chasing nested convex bodies nearly optimally

    Sebastien Bubeck, Boaz Klartag, Yin Tat Lee, Yuanzhi Li, and Mark Sellke. Chasing nested convex bodies nearly optimally. In Proceedings of SODA, pages 1496–1508, 2020

    work page 2020

  3. [3]

    Optimization of mobile sensor coverage with UA Vs

    Christelle Caillouet, Frédéric Giroire, and Tahiry Razafindralambo. Optimization of mobile sensor coverage with UA Vs. In IEEE INFOCOM 2018-IEEE Conference on Computer Communications Workshops , pages 622–627. IEEE, 2018

    work page 2018

  4. [4]

    A PTAS to minimize mobile sensor movement for target coverage problem

    Zhiyin Chen, Xiaofeng Gao, Fan Wu, and Guihai Chen. A PTAS to minimize mobile sensor movement for target coverage problem. In IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications, pages 1–9, 2016. doi:10.1109/INFOCOM.2016.7524334

    work page doi:10.1109/infocom.2016.7524334 2016

  5. [5]

    On convex body chasing

    Joel Friedman and Nathan Linial. On convex body chasing. Discrete & Computational Geometry , 9(3):293––321, 1993

    work page 1993

  6. [6]

    Pan and scan: Configuring cameras for coverage

    Matthew P Johnson and Amotz Bar-Noy. Pan and scan: Configuring cameras for coverage. In 2011 Proceedings IEEE INFOCOM , pages 1071–1079. IEEE, 2011

    work page 2011

  7. [7]

    A survey of coverage problems in wireless sensor networks

    Liang Junbin, Ming LIU, and Xiaoyan KUI. A survey of coverage problems in wireless sensor networks. Sensors and Transducers, 163:240–246, 01 2014

    work page 2014

  8. [8]

    Minimizing movement for target coverage and network connectivity in mobile sensor networks

    Zhuofan Liao, Jianxin Wang, Shigeng Zhang, Jiannong Cao, and Geyong Min. Minimizing movement for target coverage and network connectivity in mobile sensor networks. IEEE Trans. on Parallel and Distributed Systems , 26(7):1971–1983, 2015

    work page 1971

  9. [9]

    Minimizing movement for target coverage in mobile sensor networks

    Zhuofan Liao, Shigeng Zhang, Jiannong Cao, Weiping Wang, and Jianxin Wang. Minimizing movement for target coverage in mobile sensor networks. In 2012 32nd International Conference on Distributed Computing Systems Workshops, pages 194–200, 2012. doi:10.1109/ICDCSW.2012.38

    work page doi:10.1109/icdcsw.2012.38 2012

  10. [10]

    Longmore, R

    Steven N. Longmore, R. P. Collins, S. Pfeifer, S. E. Fox, M. Mulero-Pázmány, F. Bezombes, A. Goodwin, M. De Juan Ovelar, J. H. Knapen, and S. A. Wich. Adapting astronomical source detection software to help de- tect animals in thermal images obtained by unmanned aerial systems. International Journal of Remote Sensing , 38(8-10):2623–2638, 2017

    work page 2017

  11. [11]

    Minimum camera barrier coverage in wireless camera sensor networks

    Huan Ma, Meng Yang, Deying Li, Yi Hong, and Wenping Chen. Minimum camera barrier coverage in wireless camera sensor networks. In 2012 Proceedings IEEE INFOCOM , pages 217–225, 2012. doi:10.1109/INFCOM. 2012.6195602

    work page doi:10.1109/infcom 2012

  12. [12]

    Srivastava

    Seapahn Meguerdichian, Farinaz Koushanfar, Miodrag Potkonjak, and Mani B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In Proceedings IEEE INFOCOM 2001 Conference on Computer Communications. 20th Annual Joint Conference of the IEEE Computer and Communications Society , volume 3, pages 1380–1387, 2001

    work page 2001

  13. [13]

    Munishwar and Nael B

    Vikram P. Munishwar and Nael B. Abu-Ghazaleh. Scalable target coverage in smart camera networks. In Proceedings of the Fourth ACM/IEEE International Conference on Distributed Smart Cameras , ICDSC ’10, page 206–213, New York, NY, USA, 2010. Association for Computing Machinery

    work page 2010

  14. [14]

    Low complexity target coverage heuristics using mobile cameras

    Azin Neishaboori, Ahmed Saeed, Khaled Harras, and Amr Mohamed. Low complexity target coverage heuristics using mobile cameras. In 2014 IEEE 11th Int. Conference on Mobile Ad Hoc and Sensor Systems , pages 217–221, 2014

    work page 2014

  15. [15]

    Harras, and Amr Mohamed

    Ahmed Saeed, Ahmed Abdelkader, Mouhyemen Khan, Azin Neishaboori, Khaled A. Harras, and Amr Mohamed. On realistic target coverage by autonomous drones. ACM Trans. Sen. Netw. , 15(3), June 2019. doi:10.1145/ 3325512

    work page 2019

  16. [16]

    A method for optimized deployment of a network of surveillance aerial drones

    Andrey V Savkin and Hailong Huang. A method for optimized deployment of a network of surveillance aerial drones. IEEE Systems Journal , 13(4):4474–4477, 2019. 24

    work page 2019

  17. [17]

    On barrier coverage in wireless camera sensor networks

    Kuei-Ping Shih, Chien-Min Chou, I-Hsin Liu, and Chun-Chih Li. On barrier coverage in wireless camera sensor networks. In 2010 24th IEEE International Conference on Advanced Information Networking and Applications , pages 873–879, 2010

    work page 2010

  18. [18]

    Energy-efficient drone coverage path planning using genetic algorithm

    Rutuja Shivgan and Ziqian Dong. Energy-efficient drone coverage path planning using genetic algorithm. In 2020 IEEE 21st International Conference on High Performance Switching and Routing (HPSR) , pages 1–6. IEEE, 2020

    work page 2020

  19. [19]

    Coverage problems in sensor networks: A survey

    Bang Wang. Coverage problems in sensor networks: A survey. ACM Comput. Surv. , 43(4), October 2011. doi:10.1145/1978802.1978811

    work page doi:10.1145/1978802.1978811 2011

  20. [20]

    Review: A survey of movement strategies for improving network coverage in wireless sensor networks

    Bang Wang, Hock Beng Lim, and Di Ma. Review: A survey of movement strategies for improving network coverage in wireless sensor networks. Comput. Commun. , 32(13–14):1427–1436, August 2009

    work page 2009

  21. [21]

    Target coverage with minimum number of camera sensors

    Pei Yao, Longkun Guo, Shuangjuan Li, and Huihong Peng. Target coverage with minimum number of camera sensors. In Proceedings of COCOA (LNCS) , volume 13135, pages 12–24. Springer LNCS, 2021

    work page 2021

  22. [22]

    Optimal drone placement and cost-efficient target coverage

    Dimitrios Zorbas, Luigi Di Puglia Pugliese, Tahiry Razafindralambo, and Francesca Guerriero. Optimal drone placement and cost-efficient target coverage. Journal of Network and Computer Applications , 75:16–31, 2016. 25

    work page 2016