DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2021.11

Illuminating the x-Axis by α-Floodlights

Authors: Bengt J. Nilsson, David Orden, Leonidas Palios, Carlos Seara, and Paweł Żyliński

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract

Given a set S of regions with piece-wise linear boundary and a positive angle α < 90°, we consider the problem of computing the locations and orientations of the minimum number of α-floodlights positioned at points in S which suffice to illuminate the entire x-axis. We show that the problem can be solved in O(n log n) time and O(n) space, where n is the number of vertices of the set S.

Cite as

Bengt J. Nilsson, David Orden, Leonidas Palios, Carlos Seara, and Paweł Żyliński. Illuminating the x-Axis by α-Floodlights. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 11:1-11:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{nilsson_et_al:LIPIcs.ISAAC.2021.11,
  author =	{Nilsson, Bengt J. and Orden, David and Palios, Leonidas and Seara, Carlos and \.{Z}yli\'{n}ski, Pawe{\l}},
  title =	{{Illuminating the x-Axis by \alpha-Floodlights}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{11:1--11:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.11},
  URN =		{urn:nbn:de:0030-drops-154444},
  doi =		{10.4230/LIPIcs.ISAAC.2021.11},
  annote =	{Keywords: Computational Geometry, Visibility, Art Gallery Problems, Floodlights}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2019.30

Local Routing in Sparse and Lightweight Geometric Graphs

Authors: Vikrant Ashvinkumar, Joachim Gudmundsson, Christos Levcopoulos, Bengt J. Nilsson, and André van Renssen

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract

Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O(1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Bose and Morin, 2004] showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega(n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O(1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O(1)-competitive routing strategy.

Cite as

Vikrant Ashvinkumar, Joachim Gudmundsson, Christos Levcopoulos, Bengt J. Nilsson, and André van Renssen. Local Routing in Sparse and Lightweight Geometric Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ashvinkumar_et_al:LIPIcs.ISAAC.2019.30,
  author =	{Ashvinkumar, Vikrant and Gudmundsson, Joachim and Levcopoulos, Christos and Nilsson, Bengt J. and van Renssen, Andr\'{e}},
  title =	{{Local Routing in Sparse and Lightweight Geometric Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.30},
  URN =		{urn:nbn:de:0030-drops-115269},
  doi =		{10.4230/LIPIcs.ISAAC.2019.30},
  annote =	{Keywords: Computational geometry, Spanners, Routing}
}

Search Results

Documents authored by Nilsson, Bengt J.

Illuminating the x-Axis by α-Floodlights

Abstract

Cite as

Local Routing in Sparse and Lightweight Geometric Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message