Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ https://publikatione...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
https://publikationen.biblioth...
Part of book or chapter of book
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Computational Geometry
Article
License: Elsevier Non-Commercial
Data sources: UnpayWall
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Computational Geometry
Article . 2008
License: Elsevier Non-Commercial
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
Computational Geometry
Article . 2008 . Peer-reviewed
License: Elsevier Non-Commercial
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2008
Data sources: zbMATH Open
https://doi.org/10.1007/118410...
Part of book or chapter of book . 2006 . Peer-reviewed
Data sources: Crossref
DBLP
Article
Data sources: DBLP
DBLP
Conference object
Data sources: DBLP
versions View all 7 versions
addClaim

Reporting Flock Patterns

Reporting flock patterns
Authors: Marc Benkert; Joachim Gudmundsson; Florian Hübner; Thomas Wolle;

Reporting Flock Patterns

Abstract

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 some explanations and hypothesis of why the algorithms behave as they do.

Keywords

box method, numerical examples, Control and Optimization, ample-points method, Pattern recognition, speech recognition, Moving point objects, algorithms, Computational geometry, Spatio-temporal data, Trajectories, Computer Science Applications, computational goemetry, Computational Mathematics, Complexity and performance of numerical algorithms, pipe method, Computational Theory and Mathematics, Numerical aspects of computer graphics, image analysis, and computational geometry, moving point objects, Geometry and Topology, complexity, Software, source code, etc. for problems pertaining to geometry

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    160
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 10%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 1%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 10%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
160
Top 10%
Top 1%
Top 10%
hybrid