{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:14Z","timestamp":1750309154759,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,11,20]],"date-time":"2023-11-20T00:00:00Z","timestamp":1700438400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Spatial Algorithms Syst."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>A moving body is a geometry that may translate and rotate over time. Computing the time-varying distance between moving bodies and surrounding static and moving objects is crucial to many application domains including safety at sea, logistics robots, and autonomous vehicles. Not only is it a relevant analytical operation in itself, but also it forms the basis of other operations, such as finding the nearest approach distance between two moving objects. Most moving objects databases represent moving objects using a point representation, and the computed temporal distance is thus inaccurate when working with large moving objects. This article presents an efficient algorithm to compute the temporal distance between a moving body and other static or moving geometries. We extend the idea of the V-Clip and Lin-Canney closest features algorithms of computational geometry to track the temporal evolution of the closest pair of features between two objects during their movement. We also present a working implementation of this algorithm in an open-source moving objects database and show, using a real-world example on AIS data, that this distance operator for moving bodies is only about 1.5 times as slow as the one for moving points while providing significant improvements in correctness and accuracy of the results.<\/jats:p>","DOI":"10.1145\/3611010","type":"journal-article","created":{"date-parts":[[2023,8,19]],"date-time":"2023-08-19T09:50:55Z","timestamp":1692438655000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On Computing the Time-varying Distance between Moving Bodies"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1751-7471","authenticated-orcid":false,"given":"Maxime","family":"Schoemans","sequence":"first","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6741-8300","authenticated-orcid":false,"given":"Mahmoud","family":"Sakr","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles, Belgium and Ain Shams University, Egypt"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1843-5099","authenticated-orcid":false,"given":"Esteban","family":"Zim\u00e1nyi","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2023,11,20]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"169","volume-title":"Newton\u2019s Methods","author":"Chabert Jean-Luc","year":"1999","unstructured":"Jean-Luc Chabert. 1999. Newton\u2019s Methods. Springer, Berlin, 169\u2013197."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/909878"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676186"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/46.6.680"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/1370949"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1109\/ROBOT.1992.220255","volume-title":"Proceedings 1992 IEEE International Conference on Robotics and Automation","author":"Pobil Angel P. Del","year":"1992","unstructured":"Angel P. Del Pobil, Miguel Angel Serna, and Juan Llovet. 1992. A new representation for collision avoidance and detection. In Proceedings 1992 IEEE International Conference on Robotics and Automation. 246\u2013247."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90039-2"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335426"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/1769708.1769737"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(99)00042-5"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0185-7"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1080\/13658816.2018.1458103"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12689-9_105"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/VRAIS.1993.378267","volume-title":"Proceedings of 1993 IEEE Research Properties in Virtual Reality Symposium","author":"Hubbard Philip M.","year":"1993","unstructured":"Philip M. Hubbard. 1993. Interactive collision detection. In Proceedings of 1993 IEEE Research Properties in Virtual Reality Symposium. 24\u201331."},{"key":"e_1_3_3_16_2","article-title":"Decomposing a polygon into simpler components","volume":"14","author":"Keil J. Mark","year":"1985","unstructured":"J. Mark Keil. 1985. Decomposing a polygon into simpler components. SIAM Journal on Computing 14 (1985), 799\u201319.","journal-title":"SIAM Journal on Computing"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1991.131723"},{"key":"e_1_3_3_18_2","first-page":"129","article-title":"Collision detection: Algorithms and applications","author":"Lin Ming C.","year":"1997","unstructured":"Ming C. Lin, Dinesh Manocha, Jon Cohen, and Stefan Gottschalk. 1997. Collision detection: Algorithms and applications. In Algorithms for Robotic Motion and Manipulation. A K Peters\/CRC Press, 129\u2013142. https:\/\/www.taylorfrancis.com\/books\/mono\/10.1201\/9781439864524\/algorithms-robotic-motion-manipulation-jean-paul-laumond-mark-overmars","journal-title":"Algorithms for Robotic Motion and Manipulation"},{"key":"e_1_3_3_19_2","first-page":"1029","volume-title":"Collision and Proximity Queries","author":"Lin Ming C.","year":"2017","unstructured":"Ming C. Lin, Dinesh Manocha, and Young J. Kim. 2017. Collision and Proximity Queries. Chapman and Hall\/CRC, 1029\u20131056."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/285857.285860"},{"key":"e_1_3_3_21_2","volume-title":"OGC Moving Features Access","author":"Consortium OGC Open Geospatial","year":"2016","unstructured":"OGC Open Geospatial Consortium. 2016. OGC Moving Features Access. http:\/\/docs.opengeospatial.org\/is\/16-120r3\/16-120r3.html"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3423597"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989226"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/218013.218076"},{"key":"e_1_3_3_25_2","doi-asserted-by":"crossref","first-page":"3324","DOI":"10.1109\/ROBOT.1994.351059","volume-title":"Proceedings of the 1994 IEEE International Conference on Robotics and Automation","author":"Quinlan Sean","year":"1994","unstructured":"Sean Quinlan. 1994. Efficient distance computation between non-convex objects. In Proceedings of the 1994 IEEE International Conference on Robotics and Automation. 3324\u20133329."},{"key":"e_1_3_3_26_2","first-page":"99","article-title":"Assessing the impacts to vessel traffic from offshore wind farms in the Thames Estuary","volume":"43","author":"Rawson Andrew","year":"2015","unstructured":"Andrew Rawson and Edward Rogers. 2015. Assessing the impacts to vessel traffic from offshore wind farms in the Thames Estuary. Zeszyty Naukowe Akademii Morskiej w Szczecinie 43 (2015), 99\u2013107.","journal-title":"Zeszyty Naukowe Akademii Morskiej w Szczecinie"},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"771","DOI":"10.1109\/ROBOT.1996.503867","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Sato Yuichi","year":"1996","unstructured":"Yuichi Sato, Mitsunori Hirata, Tsugito Maruyama, and Yuichi Arita. 1996. Efficient collision detection using fast distance-calculation algorithms for convex and non-convex objects. In Proceedings of IEEE International Conference on Robotics and Automation. 771\u2013778."},{"key":"e_1_3_3_28_2","first-page":"12","volume-title":"Proceedings of the 37th IEEE International Conference on Data Engineering","author":"Schoemans Maxime","year":"2021","unstructured":"Maxime Schoemans, Mahmoud Sakr, and Esteban Zim\u00e1nyi. 2021. Implementing rigid temporal geometries in moving object databases. In Proceedings of the 37th IEEE International Conference on Data Engineering. 12."},{"key":"e_1_3_3_29_2","first-page":"287","volume-title":"VLDB","author":"Tao Yufei","year":"2002","unstructured":"Yufei Tao, Dimitris Papadias, and Qiongmao Shen. 2002. Continuous nearest neighbor search. In VLDB. 287\u2013298."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574070"},{"key":"e_1_3_3_31_2","doi-asserted-by":"crossref","first-page":"1522","DOI":"10.1631\/jzus.2006.A1522","article-title":"New fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram","volume":"7","author":"Yang Cheng-lei","year":"2006","unstructured":"Cheng-lei Yang, Meng Qi, Xiangxu Meng, Xue-qing Li, and Jia-ye Wang. 2006. New fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram. Journal of Zhejiang University Science 7 (2006), 1522\u20131529.","journal-title":"Journal of Zhejiang University Science"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406534"}],"container-title":["ACM Transactions on Spatial Algorithms and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611010","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3611010","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:50:52Z","timestamp":1750287052000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3611010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,20]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3611010"],"URL":"https:\/\/doi.org\/10.1145\/3611010","relation":{},"ISSN":["2374-0353","2374-0361"],"issn-type":[{"type":"print","value":"2374-0353"},{"type":"electronic","value":"2374-0361"}],"subject":[],"published":{"date-parts":[[2023,11,20]]},"assertion":[{"value":"2022-09-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}