{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T05:26:21Z","timestamp":1750137981272},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2018,6]]},"abstract":"<jats:p> One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al.<jats:sup>2<\/jats:sup> introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments. <\/jats:p><jats:p> We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of [Formula: see text] moving entities in [Formula: see text], specified by linear interpolation in a sequence of [Formula: see text] time stamps, we show that all maximal groups can be computed in [Formula: see text] time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of [Formula: see text] in the running time, where [Formula: see text] denotes the inverse Ackermann function. In higher dimensions, we can compute all maximal groups in [Formula: see text] time (for any constant number of dimensions), regardless of whether the time stamps of entities are the same or not. <\/jats:p><jats:p> We also show that one [Formula: see text] factor can be traded for a much higher dependence on [Formula: see text] by giving a [Formula: see text] algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on [Formula: see text] and linear dependence on [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0218195918600051","type":"journal-article","created":{"date-parts":[[2018,7,12]],"date-time":"2018-07-12T21:58:56Z","timestamp":1531432736000},"page":"181-196","source":"Crossref","is-referenced-by-count":8,"title":["A Refined Definition for Groups of Moving Entities and Its Computation"],"prefix":"10.1142","volume":"28","author":[{"given":"Marc","family":"van Kreveld","sequence":"first","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maarten","family":"L\u00f6ffler","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Staals","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lionov","family":"Wiratma","sequence":"additional","affiliation":[{"name":"Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands"},{"name":"Department of Informatics, Parahyangan Catholic University, Bandung, Indonesia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2018,7,12]]},"reference":[{"key":"S0218195918600051BIB002","first-page":"75","volume":"6","author":"Buchin K.","year":"2015","journal-title":"J. Comput. Geom."},{"key":"S0218195918600051BIB003","first-page":"725","volume-title":"Springer Handbook of Geographic Information","author":"Gudmundsson J.","year":"2012"},{"key":"S0218195918600051BIB004","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-1629-6"},{"key":"S0218195918600051BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2007.10.003"},{"key":"S0218195918600051BIB007","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-006-0002-z"},{"key":"S0218195918600051BIB009","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2014.889834"},{"key":"S0218195918600051BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87473-7_6"},{"key":"S0218195918600051BIB011","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453971"},{"key":"S0218195918600051BIB012","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2015.1098651"},{"key":"S0218195918600051BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_21"},{"key":"S0218195918600051BIB015","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.1054"},{"key":"S0218195918600051BIB016","first-page":"723","volume":"3","author":"Li Z.","year":"2010","journal-title":"PVLDB"},{"key":"S0218195918600051BIB017","doi-asserted-by":"publisher","DOI":"10.1145\/1989734.1989741"},{"key":"S0218195918600051BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/11596448_21"},{"key":"S0218195918600051BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2005.04.006"},{"key":"S0218195918600051BIB023","volume-title":"Davenport\u2013Schinzel Sequences and Their Geometric Applications","author":"Sharir M.","year":"1995"},{"key":"S0218195918600051BIB024","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-013-9511-3"},{"key":"S0218195918600051BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37583-5"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195918600051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:01:17Z","timestamp":1565114477000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195918600051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":18,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2018,7,12]]},"published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1142\/S0218195918600051"],"URL":"https:\/\/doi.org\/10.1142\/s0218195918600051","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}