Density Approximation for Moving Groups

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review


Sets of moving entities can form groups which travel together for significant amounts of time. Tracking such groups is an important analysis task in a variety of areas, such as wildlife ecology, urban transport, or sports analysis. Correspondingly, recent years have seen a multitude of algorithms to identify and track meaningful groups in sets of moving entities. However, not only the mere existence of one or more groups is an important fact to discover; in many application areas the actual shape of the group carries meaning as well. In this paper we initiate the algorithmic study of the shape of a moving group. We use kernel density estimation to model the density within a group and show how to efficiently maintain an approximation of this density description over time. Furthermore, we track persistent maxima which give a meaningful first idea of the time-varying shape of the group. By combining several approximation techniques, we obtain a kinetic data structure that can approximately track persistent maxima efficiently.

Original languageEnglish
Title of host publicationAlgorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings
Subtitle of host publication18th International Symposium, WADS 2023
EditorsPat Morin, Subhash Suri
Number of pages14
Publication statusPublished - Jul 2023

Publication series

NameLecture Notes in Computer Science (LNCS)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Research at Princeton Univ. was partially supported by a gift from Microsoft. Research at Univ. of California, Irvine was supported by NSF Grant 2212129. Supported by the National Science Foundation grant CCF 2046730. Supported by the National Science Foundation grant CCF 2107434. Supported by DFG grant DI 2041/2. Work supported by Independent Research Fund Denmark, grant 9131-00113B. Acknowledgement. The authors thank Merav Parter for raising the question of designing distance sensitivity oracles that require only subquadratic space. This project received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (Grant agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)”). Acknowledgments. This work was supported, in part, by MUR of Italy, under Projects PRIN 20174LF3T8 (AHeAD: Efficient Algorithms for HArnessing Networked Data), and PNRR CN00000013 (National Centre for HPC, Big Data an d Quantum Computing), and by the University of Padova under Project SID 2020 (RATED-X: Resource-Allocation TradEoffs for Dynamic and eXtreme data). Acknowledgments. We thank Bernd Gärtner for his valuable insights and feedback. This research was supported by the Swiss National Science Foundation under project no. 204320. Keywords: Wiener Index · Optimum communication spanning tree · Minimum routing cost spanning tree This work was partially supported by Grant 2016116 from the United States – Israel Binational Science Foundation. Work by P. Carmi and O. Luwisch was partially supported by the Lynn and William Frankel Center for Computer Sciences. Work by J. Mitchell was partially supported by NSF (CCF-2007275) and by DARPA (Lagrange). This work was partially supported by JSPS KAKENHI Grant Numbers JP19K11814, JP20H05793, JP20H05795, JP20K11670, JP20K11692, JP21H03397, JP22H05001, JP23K10982. A full version is available at MdB is supported by the Dutch Research Council (NWO) through Gravitation grant NETWORKS-024.002.003. Partially supported by project PID2019-104129GB-I00/MCIN/AEI/10.13039/ 501100011033 of the Spanish Ministry of Science and Innovation. Work by D.H. has been supported in part by the Israel Science Foundation (grant no. 1736/19), by NSF/US-Israel-BSF (grant no. 2019754), by the Israel Ministry of Science and Technology (grant no. 103129), by the Blavatnik Computer Science Research Fund, and by the Yandex Machine Learning Initiative for Machine Learning at Tel Aviv University. Tereza Klimoˇsová is supported by the Center for Foundations of Modern Computer Science (Charles Univ. project UNCE/SCI/004) and by GACR grant 22-19073S. This work is partially supported by NSF grant CCF 2049010. This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MSIT) (No.RS-2023-00209069). by the Natural Sciences and Engineering Research Council of Canada Supported in part by the Independent Research Fund Denmark, Natural Sciences, grant DFF-0135-00018B and in part by the Innovation Fund Denmark, grant 9142-00001B, Digital Research Centre Denmark, project P40: Online Algorithms with Predictions. Most proofs from Sects. 3 and 4 are omitted. See [6] for full proofs. M. Chrobak—Research partially supported by National Science Foundation grant CCF-2153723. in part by NSF grant CCF- Acknowledgments. We thank the anonymous reviewers for their careful reading and insightful comments. This research is supported in part by Taiwan NSTC Grant 110-2221-E-007-043. This research was supported in part by NSF under Grants CCF-2005323 and CCF-2300356. A full version of this paper is available at

FundersFunder number
Blavatnik Research Fund in Computer Science
Center for Foundations of Modern Computer ScienceUNCE/SCI/004
Digital Research Centre Denmark
Lynn and William Frankel Center for Computer Sciences
Yandex Machine Learning Initiative for Machine Learning
National Science FoundationCCF-2153723, 2212129, CCF 2049010, CCF-2300356, CCF-2005323, CCF 2107434, CCF-2007275, CCF 2046730
Defense Advanced Research Projects Agency
California Community Foundation
United States-Israel Binational Science Foundation
European Union's Horizon 2020 - Research and Innovation Framework Programme101019564
Natural Sciences and Engineering Research Council of Canada
European Research Council
Deutsche ForschungsgemeinschaftDI 2041/2
Japan Society for the Promotion of ScienceJP20K11670, JP20K11692, JP19K11814, JP22H05001, JP20H05793, JP20H05795, JP21H03397, JP23K10982
Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung204320
Grantová Agentura České Republiky22-19073S
Nederlandse Organisatie voor Wetenschappelijk OnderzoekNETWORKS-024.002.003
Italian Ministero dell’ Istruzione, Università e RicercaPNRR CN00000013, PRIN 20174LF3T8
University of Padova
Ministry of Science, ICT and Future Planning
National Research Foundation of Korea
Israel Science Foundation1736/19
Tel Aviv University
Ministerio de Ciencia e Innovación
Ministry of Science and Technology, Israel103129
Danmarks Frie Forskningsfond9131-00113B
Exploratory Research Center on Life and Living Systems, National Institutes of Natural SciencesDFF-0135-00018B
National Science and Technology Council110-2221-E-007-043


    • Group density
    • Quadtrees
    • Topological persistence


    Dive into the research topics of 'Density Approximation for Moving Groups'. Together they form a unique fingerprint.

    Cite this