Approximate Hotspots of Orthogonal Trajectories

DOI10.3233/FI-2019-1818zbMATH Open1423.68554arXiv1710.05185WikidataQ127540313 ScholiaQ127540313MaRDI QIDQ5241410

Ali Gholami Rudi

Publication date: 31 October 2019

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Abstract: 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(nlo{g}^{3}n)$ and approximation factor $1/2$.

Full work available at URL: https://arxiv.org/abs/1710.05185

zbMATH Keywords

computational geometrykinetic tournamenttrajectory hotspots

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.) (68U35) Approximation algorithms (68W25)

This page was built for publication: Approximate Hotspots of Orthogonal Trajectories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5241410)