{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T16:08:14Z","timestamp":1782576494121,"version":"3.54.5"},"reference-count":57,"publisher":"SAGE Publications","issue":"10","license":[{"start":{"date-parts":[[2016,2,15]],"date-time":"2016-02-15T00:00:00Z","timestamp":1455494400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>We present a fundamental framework for organizing exploration, coverage, and surveillance by a swarm of robots with limited individual capabilities, based on triangulating an unknown environment with a multi-robot system. Locally, an individual triangle is easy for a single robot to manage and covers a small area; globally, the topology of the triangulation approximately captures the geometry of the entire environment. Combined, a multi-robot system can explore, map, navigate, and patrol. Algorithms can store information in triangles that the robots can read and write as they run their algorithms. This creates a physical data structure (PDS) that is both robust and versatile.<\/jats:p>\n                  <jats:p>We study distributed approaches to triangulating an unknown, two-dimensional Euclidean space using a multi-robot network. The resulting PDS is a compact representation of the workspace, contains distributed knowledge of each triangle, encodes the dual graph of the triangulation, and supports reads and writes of auxiliary data. The ability to store and process this auxiliary information enables the simple robots to solve complex problems. We develop distributed algorithms for dual-graph navigation, patrolling, construction of a topological Voronoi tessellation, and location of the geodesic centers in non-convex regions. We provide theoretical performance guarantees for the quality of constructed triangulation and the connectivity of a dual graph in the triangulation. In addition, we show that the path lengths of the physical navigation are within a constant factor of the shortest-path Euclidean distance. We validate these theoretical results with simulations and experiments with a dozen or more robots.<\/jats:p>","DOI":"10.1177\/0278364915624974","type":"journal-article","created":{"date-parts":[[2016,2,15]],"date-time":"2016-02-15T21:39:08Z","timestamp":1455572348000},"page":"1234-1260","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":25,"title":["Structured triangulation in multi-robot systems: Coverage, patrolling, Voronoi partitions, and geodesic centers"],"prefix":"10.1177","volume":"35","author":[{"given":"Seoung Kyou","family":"Lee","sequence":"first","affiliation":[{"name":"Department of Computer Sciences, Rice University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S\u00e1ndor P.","family":"Fekete","sequence":"additional","affiliation":[{"name":"Department of Computer Science, TU Braunschweig, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"McLurkin","sequence":"additional","affiliation":[{"name":"Department of Computer Sciences, Rice University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2016,2,15]]},"reference":[{"key":"bibr1-0278364915624974","volume-title":"The theory of search games and rendezvous","author":"Alpern S","year":"2003"},{"key":"bibr2-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553882"},{"key":"bibr3-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1307145"},{"key":"bibr4-0278364915624974","first-page":"51","volume-title":"Algorithms for Sensor Systems - 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS)","author":"Becker A","year":"2013"},{"key":"bibr5-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907856"},{"key":"bibr6-0278364915624974","first-page":"16","volume-title":"31st International Symposium on Computational Geometry (SoCG)","author":"Becker A","year":"2015"},{"key":"bibr7-0278364915624974","doi-asserted-by":"crossref","unstructured":"Becker A, Fekete SP, Kr\u00f6ller A, (2013b) Triangulating unknown environments using robot swarms. In: 29th Annual ACM Symposium Computational Geometry (SoCG). Rio de Janeiro, Brazil, 17\u201320 June 2013, pp. 345\u2013346. Video available at http:\/\/imaginary.org\/film\/triangulating-unknown-environments-using-robot-swarms.","DOI":"10.1145\/2462356.2462360"},{"key":"bibr8-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1142\/9789814355858_0002"},{"key":"bibr9-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32723-0_5"},{"key":"bibr10-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2009.2024941"},{"key":"bibr11-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2010.5652851"},{"key":"bibr12-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509696"},{"key":"bibr13-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844100"},{"key":"bibr14-0278364915624974","first-page":"4244","volume-title":"47th IEEE Conference on Decision and Control (CDC)","author":"Caicedo-Nuez C","year":"2008"},{"key":"bibr15-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824698"},{"key":"bibr16-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2170753"},{"key":"bibr17-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509347"},{"key":"bibr18-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_30"},{"key":"bibr19-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-010-9193-y"},{"key":"bibr20-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22935-0_18"},{"key":"bibr21-0278364915624974","first-page":"82","volume-title":"17th Canadian Conference on Computational Geometry","author":"Fekete SP","year":"2005"},{"key":"bibr22-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137926"},{"key":"bibr23-0278364915624974","first-page":"6","volume-title":"3rd International Workshop on Algorithmic Aspects Wireless Sensor Networks (ALGOSENSORS)","author":"Fekete SP","year":"2007"},{"key":"bibr24-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27820-7_12"},{"key":"bibr25-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36065-7_5"},{"key":"bibr26-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"bibr27-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509263"},{"key":"bibr28-0278364915624974","volume-title":"AAAI Spring Symposium: Multirobot Systems and Physical Data Structures","author":"Ghoshal A","year":"2011"},{"key":"bibr29-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45058-0_6"},{"key":"bibr30-0278364915624974","first-page":"49","volume-title":"Proceedings of the IJCAI Workshop on Reasoning, Representation, and Learning in Computer Games","author":"Kallmann M","year":"2005"},{"key":"bibr31-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2010.11.002"},{"key":"bibr32-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2003.1249654"},{"key":"bibr33-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/11552246_13"},{"key":"bibr34-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31955-9_3"},{"key":"bibr35-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109668"},{"key":"bibr36-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02094-0_18"},{"key":"bibr37-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2015.7353406"},{"key":"bibr38-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907155"},{"key":"bibr39-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6943104"},{"key":"bibr40-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1145\/1077391.1077393"},{"key":"bibr41-0278364915624974","volume-title":"Analysis and implementation of distributed algorithms for multi-robot systems","author":"McLurkin J","year":"2008"},{"key":"bibr42-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2009.5354296"},{"key":"bibr43-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/TE.2012.2222646"},{"key":"bibr44-0278364915624974","first-page":"399","volume-title":"Proc. 7th International Symposium on Distributed Autonomous Robotic Systems (DARS)","author":"McLurkin J","year":"2004"},{"key":"bibr45-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139433"},{"key":"bibr46-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/11839088_11"},{"key":"bibr47-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/1-4020-3389-3_24"},{"key":"bibr48-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5979561"},{"key":"bibr49-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2012.2201293"},{"key":"bibr50-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2179580"},{"key":"bibr51-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2008.4739194"},{"key":"bibr52-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1126\/science.1254295"},{"key":"bibr53-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2008.10.023"},{"key":"bibr54-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1023\/B:AURO.0000033970.96785.f2"},{"key":"bibr55-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908095833"},{"key":"bibr56-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-008-0016-2"},{"key":"bibr57-0278364915624974","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224578"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915624974","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364915624974","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915624974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:18:58Z","timestamp":1777457938000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364915624974"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,15]]},"references-count":57,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1177\/0278364915624974"],"URL":"https:\/\/doi.org\/10.1177\/0278364915624974","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,15]]}}}