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.
In this paper we study the problem of finding hotspots , i.e. regions in which a moving entity has spent a significant amount of time , for polygonal trajectories . 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). Limiting ourselves to the case in which the entity moves in a direction parallel either to the x or the y-axis , We present an approximation algorithm with the time complexity O(n \log^3 n) and approximation factor 1/ 2.
D
of polygonal two-dimensional trajectories
A
, for polygonal trajectories
D
,
R
We present an approximation algorithm with the time complexity O(n \log n) and approximation factor 1/4 for orthogonal trajectories,
Limiting ourselves to the case
D
to
R
. We also present a
, We present an approximation algorithm with the time complexity O(n \log^3 n) and approximation factor
R
4-approximation algorithm for finding axis-parallel cube hotspots of fixed side length for orthogonal three-dimensional trajectories.
2.