Hussein Kazemi (LaBRI)
Title: Trajectory visibility at first sight
Abstract:
Let P be a simple polygon with n vertices, and let two moving entities q(t) and r(t) travel at constant (possibly distinct) speeds vq and vr along line-segment trajectories τq and τr inside P. We study the exact first-visibility time t∗= min t≥0: q(t) r(t) ⊆P, the earliest moment at which the segment joining q(t) and r(t) lies entirely within P.
Prior work by Eades et al. focused on this question in the setting of a simple polygon. They gave a one-shot decision algorithm running in O(n) time. For a stationary entity and a moving one, they suggested a structure that, after O(n log n) pre-processing, answers the decision query in O(log n) time, requiring O(n) space. In addition, for moving entities, after preprocessing time of O(n log⁵ n), they construct a data structure with O(n^{3/4} log³ n) query time and O(n log⁵ n) space. Variants for polygonal domains with holes or when entities cross the boundary of P lie beyond our scope.
In this work, we go beyond the decision to compute t* exactly under three models for a simple polygon P. When both trajectories are known in advance, we preprocess P in O(n) time and space and thereafter answer each query in O(log n) time. If one trajectory τr is fixed while τq is given as query, we build a structure in O(n log n) time and space that computes t∗in O(log² n) time per query. In a setting where the trajectories are not known in advance, we develop a randomized structure with O(n^{1+ε}) expected pre-processing time and O(n) space, achieving an O(√n polylog(n)) expected query time for any fixed ε > 0.