Approximate Discontinuous Trajectory Hotspots

Abstract

A hotspot is an axis-aligned square of fixed side length $s$, the duration of the presence of an entity moving in the plane in which is maximised. An exact hotspot of a polygonal trajectory with $n$ edges can be found in $O(n^2)$. Defining a $c$-approximate hotspot as an axis-aligned square of side length $cs$, in which the duration of the entity's presence is no less than that of an exact hotspot, in this paper we present an algorithm to find a $(1+\epsilon )$-approximate hotspot of a polygonal trajectory with the time complexity $O(\frac{n\varphi }{\epsilon }\log \frac{n\varphi }{\epsilon })$, where $\varphi$ is the ratio of average trajectory edge length to $s$.