Published in Volume XXIX, Issue 2, 2019, pages 185-201, doi: 10.7561/SACS.2019.2.185
Authors: A.G. Rudi
Abstract
A stay point of a moving entity is a region in which it spends a significant amount of time. In this paper, we identify all stay points of an entity in a certain time interval, where the entity is allowed to leave the region but it should return within a given time limit. This definition of stay points seems more natural in many applications of trajectory analysis than those that do not limit the time of entity’s absence from the region. We present an O(n log n) algorithm for trajectories in R1 with n vertices and a (1 + ε)-approximation algorithm for trajectories in R2 to identify all such stay points. Our algorithm runs in O(kn2), where k depends on ε and the ratio of the duration of the trajectory to the allowed gap time. We also present an algorithm to answer stay point queries in logarithmic time, after an O(kn log n) time preprocessing.
Full Text (PDF)References
[1] F.J.M. Arboleda, V. Bogorny, H. Patio. SMoT+NCS – Algorithm for Detecting Non-continuous Stops. Computing and Informatics 3(2), 283-306, 2017. doi:10.4149/cai_2017_2_283.
[2] S.W. Bae. An Almost Optimal Algorithm for Voronoi Diagrams of Non-Disjoint Line Segments. Computational Geometry 52, 34-43, 2016. doi:10.1016/J.COMGEO.2015.11.002.
[3] M. Benkert, B. Djordjevic, J. Gudmundsson, T. Wolle. Finding Popular Places. International Journal of Computational Geometry and Applications 20(1), 19-42, 2010. doi:10.1142/S0218195910003189.
[4] B. Chazelle, H. Edelsbrunner. An Optimal Algorithm for Intersecting Line Segments in the Plane. Journal of the ACM 39(1), 1-54, 1992. doi:10.1145/147508.147511.
[5] M.L. Damiani, H. Issa, F. Cagnacci. Extracting Stay Regions with Uncertain Boundaries from GPS Trajectories – A Case Study in Animal Ecology. In ACM International Conference on Advances in Geographic Information Systems, 253-262, 2014. doi:10.1145/2666310.2666417.
[6] B. Djordjevic, J. Gudmundsson. Detecting Areas Visited Regularly. In M.T. Thai, S. Sahni (Eds.) Computing and Combinatorics (COCOON 2010), Lecture Notes in Computer Science 6196, 244-253, 2010. doi:10.1007/978-3-642-14031-0_28.
[7] B. Djordjevic, J. Gudmundsson, A. Pham, T. Wolle. Detecting Regular Visit Patterns. Algorithmica 60(4), 829{852, 2011. doi:10.1007/S00453-009-9376-2.
[8] M. Fort, J.A. Sellarès, N. Valladares. Computing and Visualizing Popular Places. Knowledge and Information Systems 40(2), 411-437, 2014. doi:10.1007/s10115-013-0639-5.
[9] J. Gudmundsson, M.J. van Kreveld, F. Staals. Algorithms for Hotspot Computation on Trajectory Data. In ACM International Conference on Advances in Geographic Information Systems (SIGSPATIAL 2013), 134-143, 2013. doi:10.1145/2525314.2525359.
[10] R. Pérez-Torres, C. Torres-Huitzil, H. Galeana-Zapién. Full On-device Stay Points Detection in Smartphones for Location-based Mobile Applications. Sensors 16(10), 1693, 2016. doi:10.3390/s16101693.
[11] A.G. Rudi. Looking for Bird Nests: Identifying Stay Points with Bounded Gaps. In The Canadian Conference on Computational Geometry, 334-339, 2018. http://www.cs.umanitoba.ca/~cccg2018/papers/session7A-p2.pdf.
[12] A.G. Rudi. Approximate Hotspots of Orthogonal Trajectories. Fundamenta Informaticae 167(4), 271-285, 2019. doi:10.3233/FI-2019-1818.
[13] Y. Zhang, Y. Lin. An Interactive Method for Identifying the Stay Points of the Trajectory of Moving Objects. Journal of Visual Communication and Image Representation 59, 387-392, 2019. doi:10.1016/J.JVCIR.2019.01.038.
[14] Y. Zheng. Trajectory Data Mining – An Overview. ACM Transactions on Intelligent Systems and Technology 6(3), 29:1{29:41, 2015. doi:10.1145/2743025.
Bibtex
@article{sacscuza:rudi2019iqrvp,
title={Identifying and Querying Regularly Visited Places},
author={A. G. Rudi},
journal={Scientific Annals of Computer Science},
volume={29},
number={2},
organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
year={2019},
pages={185–201},
publisher={Alexandru Ioan Cuza University Press, Ia\c si},
doi={10.7561/SACS.2019.2.185}
}