Hainzl, E.-M., Löffler, M., Perz, D., Tkadlec, J., & Wallinger, M. (2022). Finding a Battleship of Uncertain Shape. In 38th European Workshop on Computational Geometry. March 14-16, 2022, Perugia, Italy. Booklet of abstracts. 38th European Workshop on Computational Geometry, Italy. https://doi.org/10.34726/4264
E192-01 - Forschungsbereich Algorithms and Complexity
-
Published in:
38th European Workshop on Computational Geometry. March 14-16, 2022, Perugia, Italy. Booklet of abstracts
-
Date (published):
2022
-
Event name:
38th European Workshop on Computational Geometry
en
Event date:
14-Mar-2022 - 16-Mar-2022
-
Event place:
Italy
-
Number of Pages:
7
-
Keywords:
Data Imprecision; Puzzles; Geometry; Uncertainty; Pattern Recognition
en
Abstract:
Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension d ∈ {1, 2}. A ship is a subset of Zd. Given a family F of ships, we say that an infinite subset X ⊂ Zd of the cells pierces F, if it intersects each translate of each ship in F (by a vector in Zd). In this work, we study the lowest possible (asymptotic) density π(F) of such a piercing subset. To our knowledge, this problem has previously been studied only in the special case ∣F∣ = 1 (a single ship). As our main contribution, we present a formula for π(F) when F consists of 2 ships of size 2 each, and we identify the toughest families in several other cases. We also implement an algorithm for finding π(F) in 1D.
en
Project title:
SFB-Teilprojekt: F5502-N26 (FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF))
-
Project (external):
Austrian Science Fund (FWF) Dutch Science Foundation (NWO)
