Trajectory Range Visibility

Consider two entities with not necessarily equal constant velocities, moving on two given piece-wise linear trajectories inside a simple polygon. The Trajectory Range Visibility problem deals with determining the sub-trajectories on which two entities become visible to each other. A more straightforward version of this problem is a decision version, specifying whether the entities can see one another, considering given constant velocities and assuming the trajectories are line segments. This version was studied by P. Eades et al. in 2020. However, the approach presented in this paper supports queries with constant velocities for non-constant complexity trajectories. In particular, given a constant query velocity for a moving entity, we specify $(1)$ All visible parts of the other entity's trajectory. $(2)$ All possible constant velocities of the other entity to become visible. Regarding line-segment trajectories, we obtain $\mathcal{O}(n \log n)$ time to specify all pairs of sub-trajectories visible to one another s.t. $n$ is the number of vertices of the polygon. Moreover, our results for a restricted case on non-constant complexity trajectories yield $\mathcal{O}(n + m(\log m + \log n))$ time, in which $m$ is the overall number of vertices of both trajectories. Regarding the unrestricted case, we provide $\mathcal{O}(n \log n + m(\log m + \log n))$ running time. We offer $\mathcal{O}(\log n)$ query time for line segment trajectories and $\mathcal{O}(\log m + k)$ for the non-constant complexity ones s.t. $k$ is the number of velocity ranges reported in the answer. Interestingly, our results require only $\mathcal{O}(n + m)$ space for non-constant complexity trajectories.