Approximate Hotspots of Orthogonal Trajectories.
In this paper we study the problem of finding hotspots of polygonal two-dimensional trajectories, i.e. regions in which a moving entity has spent a significant amount of time. The fastest optimal algorithm, due to Gudmundsson, van Kreveld, and Staals (2013), finds an axis-parallel square hotspot of fixed side length in $O(n^2)$. We present an approximation algorithm with the time complexity $O(n \log n)$ and approximation factor $1/4$ for orthogonal trajectories, in which the entity moves in a direction parallel either to the $x$ or to the $y$-axis. We also present a $1/4$-approximation algorithm for finding axis-parallel cube hotspots of fixed side length for orthogonal three-dimensional trajectories.
Publisher URL: http://arxiv.org/abs/1710.05185