Abstract

We study the problem of testing whether two entities moving along different piece-wise linear trajectories among polygonal obstacles are, at any time, mutually visible. We study several variants, depending on whether or not the obstacles form a simple polygon, trajectories may intersect the polygon edges, and both or only one of the entities are moving.

For constant complexity trajectories contained in a simple polygon with \(n\) vertices, we provide an \(O(n)\) time algorithm to test if there is a time at which the entities can see each other. If the polygon contains holes, we present an \(O(n \log n)\) algorithm. We show that this is tight. We then consider storing the obstacles in a data structure, such that queries consisting of two line segments can be efficiently answered. We show that for all variants it is possible to answer queries in sublinear time using polynomial space and preprocessing time.

Corresponding Publications

Trajectory Visibility

Patrick Eades, Ivor van der Hoog, Maarten Löffler, Frank Staals

Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Download Local Copy View Slides Export Citation

@incollection{trajectoryvisibility2020,
  author = {Eades, Patrick and van der Hoog, Ivor and L{\"o}ffler, Maarten
                 and Staals, Frank},
  title = {Trajectory Visibility},
  booktitle = {Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory},
  year = {2020},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  location = {Torshaven, Faroe Islands (online)},
  category = {datastructures},
  url = {https://doi.org/10.4230/LIPIcs.SWAT.2020.23},
  doi = {10.4230/LIPIcs.SWAT.2020.23},
  pages = {23:1--23:22},
  volume = {162},
}