Characterization of Optimal Trajectories in ℝ3

Abstract

We characterize the set of all trajectories \(\mathcal{T}\) of an object t moving in a given corridor Y that are furthest away from a family \(\mathbb{ S} =\{ S\} \) of fixed unfriendly observers. Each observer is equipped with a convex open scanning cone K(S) with vertex S. There are constraints on the multiplicity of covering the corridor Y by the cones K and on the “thickness” of the cones. In addition, pairs S, S′ for which [S, S′] ⊂ (K(S) ∩ K(S′)) are not allowed. The original problem \(\max\nolimits _{\mathcal{T}} \min \{d(t, S): t \in \mathcal{T}, S \in \mathbb{S}\}\), where d(t, S) = ∥t − S∥ for t ∈ K(S) and d(t,S) = +∞ for t ∉ K(S), is reduced to the problem of finding an optimal route in a directed graph whose vertices are closed disjoint subsets (boxes) from \(Y\backslash { \cup _S}K\left( S \right)\). Neighboring (adjacent) boxes are separated by some cone K(S). An edge is a part \({\cal T}\left( S \right)\) of a trajectory \({\cal T}\) that connects neighboring boxes and optimally intersects the cone K(S). The weight of an edge is the deviation of S from \({\cal T}\left( S \right)\). A route is optimal if it maximizes the minimum weight.