Reporting flock patterns
type: Item
instance of: scholarly article
title: Reporting flock patterns
zbMATH Open document ID: 1163.65011
author: Marc Benkert
author: Joachim Gudmundsson
author: Florian Hübner
author: Thomas Wolle
published in: Computational Geometry
publication date: 2008-09-19T00:00:00Z
full work available at URL: https://publikationen.bibliothek.kit.edu/1000005166/756324
review text: The authors discuss algorithms to detect flocks in moving objects. They start with a set of \(n\) identities in the plane and the position of the entities at time steps \(t_1,\dots, t_\tau\). It is supposed that these time steps are taken synchronously for all the identities and that the movement between the steps is linear at constant speed. Given integers \(m, k\) and \(r>0\), a \textit{flock} is a set of \(m\) entities such that during a \(k\)-length time, all of the entities belong to a (moving) ball of radious \(r\). The main problem is then how to detect all possible flocks from the data. The main idea of the article is, for each entity \(p\) and a \(k\)-length interval \([t_i,t_j]\), \(j-i+1\geq k\), let \((x_l,y_l)\) the possition of \(p\) at discrete time \(t_l\). Then consider the vector \((x_i,y_i,x_{i+1},y_{i+1},\dots,x_j,y_j)\) in a higher dimensional space. A flock is then a set of \(m\) entities whose corresponding vectors that are close in this higher space. In order to work with these objects, one has to be careful on how to describe the spatial objects, since the complexity increases exponentially in \(k\). The authors use a specific data structure called skip-quadtree. Some queries over these trees and operations can be done in constant time \(n\) for the model of computation assumed in the article. A set of different algorithms to compute flocks within this specific model is provided. These algorithms are approximate, they will correctly report all the flocks but there may be some detected fake-flocks, that are flocks for a radius \(\Delta r\), where \(\Delta\) may be \(\sqrt{8}+\varepsilon\) (the box method), \(2+\varepsilon\) (the pipe method) and \((1+\varepsilon)\) (ample-points method). After describing the algorithms and giving theoretical complexity, a brief discussion on related problems follows. Finally, there is a section of experiments where it is shown how the algorithms behave in practice under a number of different situations and so…
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 51-04
Mathematics Subject Classification ID: 68T10
Mathematics Subject Classification ID: 65Y20
zbMATH DE Number: 5345378
zbMATH Keywords: moving point objects
zbMATH Keywords: Trajectories
zbMATH Keywords: Spatio-temporal data
zbMATH Keywords: computational goemetry
zbMATH Keywords: numerical examples
zbMATH Keywords: complexity
zbMATH Keywords: algorithms
zbMATH Keywords: box method
zbMATH Keywords: pipe method
zbMATH Keywords: ample-points method
MaRDI profile type: Publication
OpenAlex ID: W2007159514
cites work: Approximate range searching
cites work: PARALLEL CONSTRUCTION OF QUADTREES AND QUALITY TRIANGULATIONS
cites work: The skip quadtree
cites work: Q4435893
cites work: Q4412282
cites work: Q4680560
cites work: Q2777829
DOI: 10.1016/J.COMGEO.2007.10.003
description: scientific article; zbMATH DE number 5345378