License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2018.13
URN: urn:nbn:de:0030-drops-88397
URL: https://drops.dagstuhl.de/opus/volltexte/2018/8839/
Go to the corresponding LIPIcs Volume Portal


Bose, Prosenjit ; Shermer, Thomas C.

Gathering by Repulsion

pdf-format:
LIPIcs-SWAT-2018-13.pdf (2 MB)


Abstract

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.

BibTeX - Entry

@InProceedings{bose_et_al:LIPIcs:2018:8839,
  author =	{Prosenjit Bose and Thomas C. Shermer},
  title =	{{Gathering by Repulsion}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{13:1--13:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8839},
  URN =		{urn:nbn:de:0030-drops-88397},
  doi =		{10.4230/LIPIcs.SWAT.2018.13},
  annote =	{Keywords: polygon, kernel, beacon attraction}
}

Keywords: polygon, kernel, beacon attraction
Collection: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 04.06.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI