<div class="csl-bib-body">
<div class="csl-entry">Hainzl, E.-M., Löffler, M., Perz, D., Tkadlec, J., & Wallinger, M. (2022). Finding a Battleship of Uncertain Shape. In <i>38th European Workshop on Computational Geometry. March 14-16, 2022, Perugia, Italy. Booklet of abstracts</i>. 38th European Workshop on Computational Geometry, Italy. https://doi.org/10.34726/4264</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/177472
-
dc.identifier.uri
https://doi.org/10.34726/4264
-
dc.description.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
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Data Imprecision
en
dc.subject
Puzzles
en
dc.subject
Geometry
en
dc.subject
Uncertainty
en
dc.subject
Pattern Recognition
en
dc.title
Finding a Battleship of Uncertain Shape
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Urheberrechtsschutz
de
dc.rights.license
In Copyright
en
dc.identifier.doi
10.34726/4264
-
dc.contributor.affiliation
Utrecht University, Netherlands (the)
-
dc.contributor.affiliation
Graz University of Technology, Austria
-
dc.contributor.affiliation
Harvard University, United States of America (the)
-
dc.relation.grantno
F5502-N26
-
dcterms.dateSubmitted
2022
-
dc.type.category
Abstract Book Contribution
-
tuw.booktitle
38th European Workshop on Computational Geometry. March 14-16, 2022, Perugia, Italy. Booklet of abstracts
-
tuw.project.title
SFB-Teilprojekt
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
dc.identifier.libraryid
AC17203752
-
dc.description.numberOfPages
7
-
tuw.author.orcid
0000-0002-6557-2355
-
tuw.author.orcid
0000-0003-0148-7722
-
tuw.author.orcid
0000-0002-2191-4413
-
dc.rights.identifier
Urheberrechtsschutz
de
dc.rights.identifier
In Copyright
en
tuw.event.name
38th European Workshop on Computational Geometry
en
dc.description.sponsorshipexternal
Austrian Science Fund (FWF)
-
dc.description.sponsorshipexternal
Dutch Science Foundation (NWO)
-
dc.relation.grantnoexternal
I 3340-N35
-
dc.relation.grantnoexternal
614.001.504
-
tuw.event.startdate
14-03-2022
-
tuw.event.enddate
16-03-2022
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.country
IT
-
tuw.event.presenter
Hainzl, Eva-Maria
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
dc.relation.isnewversionof
https://doi.org/10.48550/arXiv.2202.08747
-
item.openaccessfulltext
Open Access
-
item.languageiso639-1
en
-
item.mimetype
application/pdf
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.openairetype
conference paper
-
item.grantfulltext
open
-
item.fulltext
with Fulltext
-
crisitem.project.funder
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
crisitem.project.grantno
F5502-N26
-
crisitem.author.dept
E104-05 - Forschungsbereich Kombinatorik und Algorithmen
-
crisitem.author.dept
Utrecht University
-
crisitem.author.dept
Graz University of Technology
-
crisitem.author.dept
Harvard University
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.orcid
0000-0002-6557-2355
-
crisitem.author.orcid
0000-0003-0148-7722
-
crisitem.author.orcid
0000-0002-2191-4413
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie
