License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2020.23
URN: urn:nbn:de:0030-drops-122701
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12270/
Eades, Patrick ;
van der Hoog, Ivor ;
Löffler, Maarten ;
Staals, Frank
Trajectory Visibility
Abstract
We study the problem of testing whether there exists a time at which two entities moving along different piece-wise linear trajectories among polygonal obstacles are 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 ?(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 ?(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.
As a critical intermediate step, we provide an efficient solution to a problem of independent interest: preprocess a convex polygon such that we can efficiently test intersection with a quadratic curve segment. If the obstacles form a simple polygon, this allows us to answer visibility queries in ?(n³/4log³ n) time using ?(nlog⁵ n) space. For more general obstacles the query time is ?(log^k n), for a constant but large value k, using ?(n^{3k}) space. We provide more efficient solutions when one of the entities remains stationary.
BibTeX - Entry
@InProceedings{eades_et_al:LIPIcs:2020:12270,
author = {Patrick Eades and Ivor van der Hoog and Maarten L{\"o}ffler and Frank Staals},
title = {{Trajectory Visibility}},
booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
pages = {23:1--23:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-150-4},
ISSN = {1868-8969},
year = {2020},
volume = {162},
editor = {Susanne Albers},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12270},
URN = {urn:nbn:de:0030-drops-122701},
doi = {10.4230/LIPIcs.SWAT.2020.23},
annote = {Keywords: trajectories, visibility, data structures, semi-algebraic range searching}
}
|
Keywords: |
|
trajectories, visibility, data structures, semi-algebraic range searching |
|
Collection: |
|
17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
12.06.2020 |
