  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
\subset Z^2$ which has been translated in the lattice $Z^2$. 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) \leq
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.
