Finding a Battleship of Uncertain Shape

Eva-Maria Hainzl; Maarten Löffler; Daniel Perz; Josef Tkadlec; Markus Wallinger

Finding a Battleship of Uncertain Shape

Eva-Maria Hainzl, Maarten Löffler, Daniel Perz, Josef Tkadlec, Markus Wallinger

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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 $din1,2$. A ship is a subset of $. Given a family $ of ships, we say that an infinite subset $Psubset of the cells pierces $, if it intersects each translate of each ship in $ (by a vector in $). In this work, we study the lowest possible (asymptotic) density of such a piercing subset.

Original language	English
Title of host publication	Proc. 38th European Workshop on Computational Geometry
Publication status	Published - 2022

Keywords

IMP
PUZ

Cite this

@inproceedings{b96fc36d615e4e3fbd49c35532a709be,

title = "Finding a Battleship of Uncertain Shape",

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 $din1,2$. A ship is a subset of $. Given a family $ of ships, we say that an infinite subset $Psubset of the cells pierces $, if it intersects each translate of each ship in $ (by a vector in $). In this work, we study the lowest possible (asymptotic) density of such a piercing subset.",

keywords = "IMP, PUZ",

author = "Eva-Maria Hainzl and Maarten L{\"o}ffler and Daniel Perz and Josef Tkadlec and Markus Wallinger",

year = "2022",

language = "English",

booktitle = "Proc. 38th European Workshop on Computational Geometry",

}

TY - GEN

T1 - Finding a Battleship of Uncertain Shape

AU - Hainzl, Eva-Maria

AU - Löffler, Maarten

AU - Perz, Daniel

AU - Tkadlec, Josef

AU - Wallinger, Markus

PY - 2022

Y1 - 2022

N2 - 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 $din1,2$. A ship is a subset of $. Given a family $ of ships, we say that an infinite subset $Psubset of the cells pierces $, if it intersects each translate of each ship in $ (by a vector in $). In this work, we study the lowest possible (asymptotic) density of such a piercing subset.

AB - 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 $din1,2$. A ship is a subset of $. Given a family $ of ships, we say that an infinite subset $Psubset of the cells pierces $, if it intersects each translate of each ship in $ (by a vector in $). In this work, we study the lowest possible (asymptotic) density of such a piercing subset.

KW - IMP

KW - PUZ

M3 - Conference contribution

BT - Proc. 38th European Workshop on Computational Geometry

ER -

Finding a Battleship of Uncertain Shape

Abstract

Keywords

Fingerprint

Cite this