DROPS

Document

DOI: 10.4230/LIPIcs.WADS.2025.10

On Geodesic Disks Enclosing Many Points

Authors: Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira, and Tyler Tuttle

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract

Let Π(n) be the largest number such that for every set S of n points in a polygon P, there always exist two points x, y ∈ S, where every geodesic disk containing x and y contains Π(n) points of S. We establish upper and lower bounds for Π(n), and show that ⌈n/5⌉ +1 ≤ Π(n) ≤ ⌈n/4⌉ +1. We also show that there always exist two points x, y ∈ S such that every geodesic disk with x and y on its boundary contains at least 16/665(n-2) ≈ ⌈(n-2)/41.6⌉ points both inside and outside the disk. For the special case where the points of S are restricted to be the vertices of a geodesically convex polygon we give a tight bound of ⌈n/3⌉ + 1. We provide the same tight bound when we only consider geodesic disks having x and y as diametral endpoints. Finally, we give a lower bound of ⌈(n-2)/36⌉+2 for the two-colored version of the problem.

Cite as

Prosenjit Bose, Guillermo Esteban, David Orden, Rodrigo I. Silveira, and Tyler Tuttle. On Geodesic Disks Enclosing Many Points. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.WADS.2025.10,
  author =	{Bose, Prosenjit and Esteban, Guillermo and Orden, David and Silveira, Rodrigo I. and Tuttle, Tyler},
  title =	{{On Geodesic Disks Enclosing Many Points}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.10},
  URN =		{urn:nbn:de:0030-drops-242414},
  doi =		{10.4230/LIPIcs.WADS.2025.10},
  annote =	{Keywords: Enclosing disks, Geodesic disks, Bichromatic}
}

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}
}

Search Results

Documents authored by Orden, David

On Geodesic Disks Enclosing Many Points

Abstract

Cite as

Illuminating the x-Axis by α-Floodlights

Abstract

Cite as

Thanks for your feedback!

Could not send message