Makespan Trade-offs for Visiting Triangle Edges

We study a primitive vehicle routing-type problem in which a fleet of nunit speed robots start from a point within a non-obtuse triangle Δ, where n ∈ \1,2,3\. The goal is to design robots' trajectories so as to visit all edges of the triangle with the smallest visitation time makespan. We begin our study by introducing a framework for subdividing Δinto regions with respect to the type of optimal trajectory that each point P admits, pertaining to the order that edges are visited and to how the cost of the minimum makespan Rₙ(P) is determined, for n∈ \1,2,3\. These subdivisions are the starting points for our main result, which is to study makespan trade-offs with respect to the size of the fleet. In particular, we define Rn,m (Δ)= maxP ∈ Δ Rₙ(P)/Rₘ(P), and we prove that, over all non-obtuse triangles Δ: (i) R1,3(Δ) ranges from √10 to $4$, (ii) R2,3(Δ) ranges from √2 to $2$, and (iii) R1,2(Δ) ranges from $5/2$ to $3$. In every case, we pinpoint the starting points within every triangle Δ that maximize Rn,m (Δ), as well as we identify the triangles that determine all inf_Δ Rn,m(Δ) and _Δ Rn,m(Δ) over the set of non-obtuse triangles. Comment: 47 pages, 27 figures