Efficient Algorithms for Battleship

Authors Loïc Crombez , Guilherme D. da Fonseca , Yan Gerard



PDF
Thumbnail PDF

File

LIPIcs.FUN.2021.11.pdf
  • Filesize: 1.7 MB
  • 15 pages

Document Identifiers

Author Details

Loïc Crombez
  • Université Clermont Auvergne, LIMOS, Aubière, France
Guilherme D. da Fonseca
  • Université Aix Marseille, LIS, France
Yan Gerard
  • Université Clermont Auvergne, LIMOS, Aubière, France

Cite AsGet BibTex

Loïc Crombez, Guilherme D. da Fonseca, and Yan Gerard. Efficient Algorithms for Battleship. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FUN.2021.11

Abstract

We consider an algorithmic problem inspired by the Battleship game. In the variant of the problem that we investigate, there is a unique ship of shape S ⊂ ℤ² which has been translated in the lattice ℤ². We assume that a player has already hit the ship with a first shot and the goal is to sink the ship using as few shots as possible, that is, by minimizing the number of missed shots. While the player knows the shape S, which position of S has been hit is not known. Given a shape S of n lattice points, the minimum number of misses that can be achieved in the worst case by any algorithm is called the Battleship complexity of the shape S and denoted c(S). We prove three bounds on c(S), each considering a different class of shapes. First, we have c(S) ≤ n-1 for arbitrary shapes and the bound is tight for parallelogram-free shapes. Second, we provide an algorithm that shows that c(S) = O(log n) if S is an HV-convex polyomino. Third, we provide an algorithm that shows that c(S) = O(log log n) if S is a digital convex set. This last result is obtained through a novel discrete version of the Blaschke-Lebesgue inequality relating the area and the width of any convex body.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Polyomino
  • digital geometry
  • decision tree
  • lattice
  • HV-convexity
  • convexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Micah Adler and Brent Heeringa. Approximating optimal binary decision trees. In 11th Approximation, Randomization and Combinatorial Optimization, APPROX 2008, pages 1-9, 2008. URL: http://dx.doi.org/10.1007/978-3-540-85363-3_1.
  2. Esther M. Arkin, Michael T. Goodrich, Joseph S. B. Mitchell, David M. Mount, Christine D. Piatko, and Steven Skiena. Point probe decision trees for geometric concept classes. In Third Workshop on Algorithms and Data Structures, WADS 1993, pages 95-106, 1993. URL: http://dx.doi.org/10.1007/3-540-57155-8_239.
  3. Esther M. Arkin, Henk Meijer, Joseph S. B. Mitchell, David Rappaport, and Steven Skiena. Decision trees for geometric models. In Nineth Annual Symposium on Computational Geometry, SoCG 1993, pages 369-378, 1993. URL: http://dx.doi.org/10.1145/160985.161167.
  4. Imre Bárány and Zoltan Füredi. On the lattice diameter of a convex polygon. Discrete Mathematics, 241(1):41-50, 2001. Selected Papers in honor of Helge Tverberg. URL: http://dx.doi.org/10.1016/S0012-365X(01)00145-5.
  5. Imre Bárány and Janos Pach. On the number of convex lattice polygons. Combinatorics, Probability and Computing, 1(4):295-302, 1992. URL: http://dx.doi.org/10.1017/S0963548300000341.
  6. Loïc Crombez, Guilherme D. da Fonseca, and Yan Gérard. Efficient algorithms to test digital convexity. In International Conference on Discrete Geometry for Computer Imagery, DGCI 2019, pages 409-419, 2019. URL: http://dx.doi.org/10.1007/978-3-030-14085-4_32.
  7. Laurent Hyafil and Ronald L. Rivest. Constructing optimal binary decision trees is NP-complete. Information Processing Letters, 5(1):15-17, 1976. URL: http://dx.doi.org/10.1016/0020-0190(76)90095-8.
  8. Daniel M. Kane, Shachar Lovett, and Shay Moran. Near-optimal linear decision trees for k-sum and related problems. Journal of the ACM, 66(3), 2019. URL: http://dx.doi.org/10.1145/3285953.
  9. Lior Rokach and Oded Maimon. Data Mining With Decision Trees: Theory and Applications. World Scientific Publishing Co., 2nd edition, 2014. Google Scholar
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