2026-08-06T12:46:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8839 2024-03-06T10:42:46Z ddc:004 open_access

Gathering by Repulsion Bose, Prosenjit Shermer, Thomas C. polygon kernel beacon attraction We consider a repulsion actuator located in an n-sided convex environment full of point particles. When the actuator is activated, all the particles move away from the actuator. We study the problem of gathering all the particles to a point. We give an O(n^2) time algorithm to compute all the actuator locations that gather the particles to one point with one activation, and an O(n) time algorithm to find a single such actuator location if one exists. We then provide an O(n) time algorithm to place the optimal number of actuators whose sequential activation results in the gathering of the particles when such a placement exists. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prosenjit Bose and Thomas C. Shermer 2018 Is Part Of LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2018.13 urn:nbn:de:0030-drops-88397 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.13 eng https://creativecommons.org/licenses/by/3.0/legalcode