2 Search Results for "Castermans, Thom"

Document
DOI: 10.4230/LIPIcs.ISAAC.2018.49
Competitive Searching for a Line on a Line Arrangement

Authors: Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We discuss the problem of searching for an unknown line on a known or unknown line arrangement by a searcher S, and show that a search strategy exists that finds the line competitively, that is, with detour factor at most a constant when compared to the situation where S has all knowledge. In the case where S knows all lines but not which one is sought, the strategy is 79-competitive. We also show that it may be necessary to travel on Omega(n) lines to realize a constant competitive ratio. In the case where initially, S does not know any line, but learns about the ones it encounters during the search, we give a 414.2-competitive search strategy.
Cite as

Quirijn Bouts, Thom Castermans, Arthur van Goethem, Marc van Kreveld, and Wouter Meulemans. Competitive Searching for a Line on a Line Arrangement. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 49:1-49:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bouts_et_al:LIPIcs.ISAAC.2018.49,
  author =	{Bouts, Quirijn and Castermans, Thom and van Goethem, Arthur and van Kreveld, Marc and Meulemans, Wouter},
  title =	{{Competitive Searching for a Line on a Line Arrangement}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{49:1--49:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.49},
  URN =		{urn:nbn:de:0030-drops-99970},
  doi =		{10.4230/LIPIcs.ISAAC.2018.49},
  annote =	{Keywords: Competitive searching, line arrangement, detour factor, search strategy}
}
Document
Multimedia Contribution
DOI: 10.4230/LIPIcs.SoCG.2017.63
Ruler of the Plane - Games of Geometry (Multimedia Contribution)

Authors: Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, and Willem Sonke

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Ruler of the Plane is a set of games illustrating concepts from combinatorial and computational geometry. The games are based on the art gallery problem, ham-sandwich cuts, the Voronoi game, and geometric network connectivity problems like the Euclidean minimum spanning tree and traveling salesperson problem.
Cite as

Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, and Willem Sonke. Ruler of the Plane - Games of Geometry (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 63:1-63:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{beekhuis_et_al:LIPIcs.SoCG.2017.63,
  author =	{Beekhuis, Sander and Buchin, Kevin and Castermans, Thom and Hurks, Thom and Sonke, Willem},
  title =	{{Ruler of the Plane - Games of Geometry}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{63:1--63:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.63},
  URN =		{urn:nbn:de:0030-drops-72400},
  doi =		{10.4230/LIPIcs.SoCG.2017.63},
  annote =	{Keywords: art gallery problem, ham-sandwich cuts, Voronoi game, traveling sales-person problem}
}
  • Refine by Author
  • 2 Castermans, Thom
  • 1 Beekhuis, Sander
  • 1 Bouts, Quirijn
  • 1 Buchin, Kevin
  • 1 Hurks, Thom
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Competitive searching
  • 1 Voronoi game
  • 1 art gallery problem
  • 1 detour factor
  • 1 ham-sandwich cuts
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact