pith. sign in

arxiv: 2605.15765 · v1 · pith:GOJUNSBCnew · submitted 2026-05-15 · 💻 cs.CG · cs.DS· cs.RO· math.OC

Optimizing Line Segment Inspection with Limited-Range Drones

Jos\'e-Miguel D\'iaz-B\'a\~nez , Jos\'e-Manuel Higes , Alina Kasiuk , Inmaculada Ventura This is my paper

Pith reviewed 2026-05-19 18:09 UTC · model grok-4.3

classification 💻 cs.CG cs.DScs.ROmath.OC
keywords drone inspectionline segment coverageNP-hardnessapproximation algorithmsmakespan minimizationbattery constraintspath planningsolar plant maintenance
0
0 comments X

The pith

The drone inspection problem for line segments is strongly NP-hard even with two drones on a straight line.

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

The paper studies how to assign inspection tours to a small fleet of battery-limited drones so that every line segment is covered and the overall completion time, or makespan, is minimized. Periodic returns to one fixed base station are required because of battery limits. A sympathetic reader would care because real-world drone tasks such as checking solar-plant pipes need fast coverage yet must respect energy constraints, and hardness results show why simple optimal schedules are unavailable. The authors establish strong NP-hardness for the case of segments lying on a line and only two drones, then give approximation algorithms whose performance is tested on varied instances.

Core claim

The problem of covering a set of line segments by tours that start and end at a single base station, using a fixed number of drones, so as to minimize the maximum tour length among the drones is strongly NP-hard even when the segments are collinear and the number of drones is two. Approximation algorithms are proposed whose computed makespans are shown to be close to optimal in computational experiments across diverse scenarios.

What carries the argument

A reduction establishing strong NP-hardness for the two-drone collinear case, together with the approximation algorithms that produce feasible tour sets whose makespan is guaranteed to be within a bounded factor of the optimum.

If this is right

  • Exact optimal schedules cannot be computed efficiently for large numbers of segments even when geometry is restricted to a line.
  • Approximation algorithms become the practical route for producing drone tour assignments that finish inspection quickly.
  • The hardness result continues to hold when the only geometric constraint is that segments lie on one line.
  • Operational planners must accept near-optimal rather than exact solutions when assigning limited-range drones to cover many segments.

Where Pith is reading between the lines

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

  • The same reduction technique may extend to show hardness for small numbers of drones in the plane, suggesting broader intractability.
  • Real deployments would benefit from hybrid approaches that combine the approximations with local search or machine-learning guidance for tour refinement.
  • If segments can be inspected at different speeds or if multiple base stations are allowed, the hardness might change and new polynomial cases could appear.

Load-bearing premise

The model assumes that battery limits force periodic returns to a single fixed base station and that minimizing makespan accurately reflects operational priorities without additional constraints such as wind, obstacles, or variable inspection times.

What would settle it

Discovery of a polynomial-time algorithm that computes an optimal makespan schedule for any set of collinear segments and exactly two drones would falsify the strong NP-hardness claim.

Figures

Figures reproduced from arXiv: 2605.15765 by Alina Kasiuk, Inmaculada Ventura, Jos\'e-Manuel Higes, Jos\'e-Miguel D\'iaz-B\'a\~nez.

Figure 1
Figure 1. Figure 1: Receiver tubes in a CSP-type solar plant. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Covering tours for two drones. Blue and red tours correspond to different drones. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Diagram for Step 1. Right-hand points yi . • Step 2: Determine the number sequence: {s ′ i = Ksi + 2c2n} 2n i=1 with K = L − 2c2n R . • Step 3: For i = 1, · · · , 2n, determine the sequence of right hand points xi , with bi = d(xi , B) that satisfies: ci + (yi − xi) + bi = s ′ i , (4) b 2 i = x 2 i +  L 3 2 . (5) • Step 4: Let αS = {ai} 2n i=1 where ai = [xi , yi ] if i even, and ai = [−yi , −xi ] if i o… view at source ↗
Figure 4
Figure 4. Figure 4: Diagram for Step 4. Final construction. It is easy to see that the construction of αS can be done in polynomial time. This result follows from the following remark and lemma. Remark 2. Notice that each ci can be obtained in constant time. Moreover, as in each step we compute yi by making a tour of length L by equation (2), and the point C is at distance L/2 from B then all yi < C as C is the (infinite) lim… view at source ↗
Figure 5
Figure 5. Figure 5: (a) Two broken segments. (b) Reassigning the tours, the global length is improved. [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: (a) Cutting a red tour. (b) Enlarging a blue tour and reducing a red tour. [PITH_FULL_IMAGE:figures/full_fig_p016_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: a) Approximation factor ∆, where ℓ(T2) is a solution received from G2D-algorithm and ℓ(T ∗ 2 ) is an optimal solution found by Gurobi™. (b) Approximation factor ∆I , where ℓ(T2) is a solution received after applying the Cutting and Enlarging strategies. To analyze how ∆ and ∆I vary with L, we rely on Theorem 5.1(c), which predicts that ∆ grows monotonically with L. There is no expected pattern for ∆I . L i… view at source ↗
Figure 8
Figure 8. Figure 8: Changes in the approximation factor of the G2D-algorithm when the maximum length of a tour L [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Interaction effect between L and homogeneity factor for ∆I . In each scenario, the segments were generated randomly with normal distribution, with mean m uniformly chosen with m ∈ [10, 100]. The density factor was divided into two levels: low density ρ ≈ 0.2 (2526 cases) and high density ρ ≈ 0.8 (780 cases). Our segment generation algorithm iteratively adds segments until achieving approximately the requir… view at source ↗
Figure 10
Figure 10. Figure 10: Impact of maximum tour length L on approximation factors for (1) the baseline G2D-algorithm (blue) and (2) the improved algorithm (orange). effects from the L factor (F = 833.755, p < 0.001) and the density factor (F = 108.273, p < 0.001). There was also an interaction effect between the factor L and the density factor (F = 127.480, p < 0.001). A post hoc Tukey HSD test revealed statistically significant … view at source ↗
Figure 11
Figure 11. Figure 11: Interaction effect between L and the density factor for the G2D algorithm. (homogeneity: F = 0.028. L-factor: F = 2.780). A post-hoc Tukey’s HSD test showed a statistically significant difference between the high density group and the low density group, with a mean difference of 264.82 seconds (p < 0.001). In [PITH_FULL_IMAGE:figures/full_fig_p023_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Interaction effect between L and the homogeneity factor for the improved algorithm. particular in the cases of low L. Our benchmarking revealed significant computational limitations in the Gurobi™ solver’s performance. In particular, in cases of high density and low L, our computational experiments revealed significant limitations in the Gurobi™ solver’s performance, reaching a maximum of time of several … view at source ↗
Figure 13
Figure 13. Figure 13: Interaction effect between L and the density factor for the Gurobi time in seconds. Something similar is happening in the second example, shown on [PITH_FULL_IMAGE:figures/full_fig_p025_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Examples of solutions provided G2D-algorithm in comparison with optimal solution. Dashed [PITH_FULL_IMAGE:figures/full_fig_p025_14.png] view at source ↗
read the original abstract

Optimization problems with drones are widely studied in a variety of civilian tasks, mainly due to their ability to traverse rough terrains and to carry cameras and other sensors for surveillance tasks. The limited battery life of these aerial robots poses challenges in operational research. In this paper, we address the following optimization problem. We are given a set of line segments (e.g. tubes in a solar plant) to inspect by drones. The objective is to detect broken pipes using artificial intelligence and path planning must be carried out efficiently. On the one hand, the limited capacity of the batteries necessitates periodic visits (tours) to a fixed base station. However, it is desirable to allocate a set of tours for each drone to ensure that the segments are covered as quickly as possible, aiming to minimize the makespan, which is the maximum time spent by any drone. We are able to prove that this optimization problem is strongly NP-hard even when the segments are positioned on a line and the scenario involves only two drones. Then, approximation algorithms are proposed. Our computational experiments demonstrate that the proposed algorithm achieves near-optimal performance across diverse operational scenarios.

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

2 major / 2 minor

Summary. The manuscript formulates the line-segment inspection problem for limited-range drones that must return to a fixed base station to recharge. The objective is to assign tours to a fleet of drones so that every segment is inspected while minimizing the makespan (maximum completion time). The authors prove that the problem remains strongly NP-hard even when all segments lie on a line and only two drones are used. They then present approximation algorithms and report computational experiments indicating near-optimal performance on diverse instances.

Significance. A correctly established strong NP-hardness result for the two-drone collinear case would justify the need for approximation methods in a geometrically simple setting and strengthen the case for heuristic approaches in operational drone planning. The reported experimental performance, if supported by reproducible code, error bars, and clear data-exclusion criteria, would indicate practical utility for infrastructure-monitoring applications such as solar-plant inspection.

major comments (2)
  1. [§3] §3 (NP-hardness reduction): The reduction establishing strong NP-hardness for two drones on a line must explicitly rule out a pseudo-polynomial dynamic program that exploits the linear order. A natural DP over prefixes of segments, remaining battery, and last return time to the base could run in O(n²B) time (B = battery capacity); the construction must ensure that battery-reset deadlines and segment lengths prevent such an algorithm from solving the problem in pseudo-polynomial time, otherwise the claimed hardness is undermined.
  2. [§4] §4 (Approximation algorithms): The approximation ratio analysis should state the precise dependence on the number of drones and on the ratio of battery capacity to total segment length; without this, it is unclear whether the guarantee remains meaningful when the number of drones is fixed at two.
minor comments (2)
  1. [§5] The experimental section should report standard deviations or confidence intervals for the makespan values and explicitly describe the instance-generation procedure and any data-exclusion rules.
  2. [Throughout] Notation for the battery capacity and return deadlines should be introduced once and used consistently; currently the abstract and hardness section appear to use slightly different symbols for the same quantities.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below and indicate the revisions planned for the next version.

read point-by-point responses

  1. Referee: [§3] §3 (NP-hardness reduction): The reduction establishing strong NP-hardness for two drones on a line must explicitly rule out a pseudo-polynomial dynamic program that exploits the linear order. A natural DP over prefixes of segments, remaining battery, and last return time to the base could run in O(n²B) time (B = battery capacity); the construction must ensure that battery-reset deadlines and segment lengths prevent such an algorithm from solving the problem in pseudo-polynomial time, otherwise the claimed hardness is undermined.

    Authors: We appreciate this observation regarding the distinction between weak and strong NP-hardness. Our reduction is from 3-Partition, a strongly NP-complete problem, and produces instances in which all numerical parameters (segment lengths and battery capacities) are polynomially bounded. We will revise the proof in §3 to explicitly argue that no O(n²B)-time DP exists: because the two drones must interleave their tours while respecting individual battery resets and a shared makespan objective, the state must encode the partition of inspected segments between the drones together with their separate battery and position information. This combinatorial partitioning prevents the state space from remaining polynomial in B, thereby preserving strong NP-hardness. The revised proof will include this argument and a brief complexity analysis of any candidate DP. revision: yes

  2. Referee: [§4] §4 (Approximation algorithms): The approximation ratio analysis should state the precise dependence on the number of drones and on the ratio of battery capacity to total segment length; without this, it is unclear whether the guarantee remains meaningful when the number of drones is fixed at two.

    Authors: We agree that the dependence should be stated explicitly. The analysis in §4 yields an approximation ratio that is a function of the number of drones k and the ratio of battery capacity B to total segment length L; the bound remains O(k · (B/L + 1)) under standard assumptions on tour construction. When k is fixed at two the ratio is therefore constant whenever B/L is bounded, which is the regime of practical interest for limited-range drones. We will add the precise functional dependence and a short corollary for the two-drone case in the revised §4. revision: yes

Circularity Check

0 steps flagged

No circularity: independent NP-hardness proof and separate approximation analysis

full rationale

The paper states a strong NP-hardness result for the two-drone line-segment case as a direct proof, followed by separately proposed approximation algorithms whose performance is then validated on instances. No step equates a derived quantity to a fitted parameter by construction, renames an input as a prediction, or relies on a self-citation chain for the load-bearing claim. The derivation remains self-contained against external benchmarks such as standard reduction techniques and experimental validation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the model implicitly assumes Euclidean distances, fixed base station, and uniform inspection cost per segment, but none are quantified or justified here.

pith-pipeline@v0.9.0 · 5753 in / 1055 out tokens · 59660 ms · 2026-05-19T18:09:37.511489+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    Annals of Operations Research , pages=

    Joint optimisation of drone routing and battery wear for sustainable supply chain development: A mixed-integer programming model based on blockchain-enabled fleet sharing , author=. Annals of Operations Research , pages=. 2023 , publisher=

    work page 2023

  2. [2]

    Operational Research , volume=

    Vehicle routing problem under safe separation distance for multiple unmanned aerial vehicle operation , author=. Operational Research , volume=. 2022 , publisher=

    work page 2022

  3. [3]

    European Journal of Operational Research , volume=

    Facility location decisions for drone delivery: A literature review , author=. European Journal of Operational Research , volume=. 2024 , publisher=

    work page 2024

  4. [4]

    Information Processing Letters , pages=

    Covering segments on a line with drones , author=. Information Processing Letters , pages=. 2024 , publisher=

    work page 2024

  5. [5]

    Theoretical Computer Science , volume=

    Optimal placement of base stations in border surveillance using limited capacity drones , author=. Theoretical Computer Science , volume=. 2022 , publisher=

    work page 2022

  6. [6]

    European Journal of Operational Research , volume=

    Solving the length constrained K-drones rural postman problem , author=. European Journal of Operational Research , volume=. 2021 , publisher=

    work page 2021

  7. [7]

    Solar energy , volume=

    Airborne shape measurement of parabolic trough collector fields , author=. Solar energy , volume=. 2013 , publisher=

    work page 2013

  8. [8]

    International Conference on Electrical Systems & Automation , pages=

    Unmanned Aerial Vehicle Path Planning Algorithms for Very High Voltage Transmission Lines Inspection , author=. International Conference on Electrical Systems & Automation , pages=. 2023 , organization=

    work page 2023

  9. [9]

    IEEE access , volume=

    Unmanned aerial systems for the oil and gas industry: Overview, applications, and challenges , author=. IEEE access , volume=. 2020 , publisher=

    work page 2020

  10. [10]

    and Corber

    Campbell, James F. and Corber. Drone arc routing problems , journal=

    work page

  11. [11]

    Transportation Research Part C: Emerging Technologies , volume=120, pages=102762, year=2020, publisher=

    Macrina, Giusy and Pugliese, Luigi Di Puglia and Guerriero, Francesca and Laporte, Gilbert , title=. Transportation Research Part C: Emerging Technologies , volume=120, pages=102762, year=2020, publisher=

    work page 2020

  12. [12]

    Detecting broken receiver tubes in CSP plants using intelligent sampling and dual loss , journal=

    P. Detecting broken receiver tubes in CSP plants using intelligent sampling and dual loss , journal=

    work page

  13. [13]

    Real Time and Post-Processing Flight Inspection by Drone: A Survey , booktitle=

    Togola, S. Real Time and Post-Processing Flight Inspection by Drone: A Survey , booktitle=

    work page

  14. [14]

    Computers and intractability: A guide to the theory of np-completeness, freeman , author=

    work page

  15. [15]

    Coverage Optimization with a Dynamic Network of Drone Relays , year=

    Arribas, Edgar and Mancuso, Vincenzo and Cholvi, Vicent , journal=. Coverage Optimization with a Dynamic Network of Drone Relays , year=

    work page

  16. [16]

    Covering segments on a line with drones , booktitle=

    Bereg, Sergey and D. Covering segments on a line with drones , booktitle=

    work page

  17. [17]

    Information Processing Letters , year=

    Covering segments on a line with drones , author=. Information Processing Letters , year=

    work page

  18. [18]

    Garey, Michael and Johnson, David , title =

    work page

  19. [19]

    Path planning algorithms for power transmission line inspection using unmanned aerial vehicles , year=

    Cui, Jingkui and Zhang, Youmin and Ma, Sha and Yi, Yingmin and Xin, Jing and Liu, Ding , booktitle=. Path planning algorithms for power transmission line inspection using unmanned aerial vehicles , year=

    work page

  20. [20]

    Multi-Tour Set Traveling Salesman Problem in Planning Power Transmission Line Inspection , year=

    Nekovář, František and Faigl, Jan and Saska, Martin , journal=. Multi-Tour Set Traveling Salesman Problem in Planning Power Transmission Line Inspection , year=

    work page

  21. [21]

    2022 , issn =

    Routing for unmanned aerial vehicles: Touring dimensional sets , journal =. 2022 , issn =

    work page 2022

  22. [22]

    and Jhaveri, Rutvij H

    Jemmali, Mahdi and Bashir, Ali Kashif and Boulila, Wadii and Melhim, Loai Kayed B. and Jhaveri, Rutvij H. and Ahmad, Jawad , journal=. An Efficient Optimization of Battery-Drone-Based Transportation Systems for Monitoring Solar Power Plant , year=

    work page

  23. [23]

    2021 , issn =

    Exact methods for the traveling salesman problem with multiple drones , journal =. 2021 , issn =

    work page 2021

  24. [24]

    Transportation Science , month =

    Morandi, Nicola and Leus, Roel and Matuschke, Jannik and Yaman, Hande , title =. Transportation Science , month =. 2023 , issue_date =

    work page 2023

  25. [25]

    On Strong NP-Completeness of Rational Problems

    Wojtczak, Dominik. On Strong NP-Completeness of Rational Problems. Computer Science -- Theory and Applications. 2018

    work page 2018

  26. [26]

    Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling Depots , year=

    Sundar, Kaarthik and Rathinam, Sivakumar , journal=. Algorithms for Routing an Unmanned Aerial Vehicle in the Presence of Refueling Depots , year=

    work page

  27. [27]

    2020 , author =

    Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions , journal =. 2020 , author =

    work page 2020

  28. [28]

    Placement and Routing Optimization for Automated Inspection With Unmanned Aerial Vehicles: A Study in Offshore Wind Farm , year=

    Chung, Hwei-Ming and Maharjan, Sabita and Zhang, Yan and Eliassen, Frank and Strunz, Kai , journal=. Placement and Routing Optimization for Automated Inspection With Unmanned Aerial Vehicles: A Study in Offshore Wind Farm , year=

    work page