Time-Windowed Contiguous Hotspot Queries

A hotspot of a moving entity is a region in which it spends a significant amount of time. Given the location of a moving object through a certain time interval, i.e. its trajectory, our goal is to find its hotspots. We consider axis-parallel square hotspots of fixed side length, which contain the longest contiguous portion of the trajectory. Gudmundsson, van Kreveld, and Staals (2013) presented an algorithm to find a hotspot of a trajectory in $O(n \log n)$, in which $n$ is the number of vertices of the trajectory. We present an algorithm for answering \emph{time-windowed} hotspot queries, to find a hotspot in any given time interval. The algorithm has an approximation factor of $1/2$ and answers each query with the time complexity $O(\log^2 n)$. The time complexity of the preprocessing step of the algorithm is $O(n)$. When the query contains the whole trajectory, it implies an $O(n)$ algorithm for finding approximate contiguous hotspots.
Comment: Updates after ICCG 2018