Approximate Discontinuous Trajectory Hotspots

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({n\phi \over \epsilon} \log {n\phi \over \epsilon})$, where $\phi$ is the ratio of average trajectory edge length to $s$.