Portal de Periódicos da CAPES

How to find a battleship

1989; Wiley; Volume: 19; Issue: 3 Linguagem: Inglês

10.1002/net.3230190306

1097-0037

Amos Fiat, Adi Shamir,

Computational Geometry and Mesh Generation

Abstract Consider a “sea” of M squares which contains (at some unknown location) a “battleship” of K squares. Both the sea and the battleship can assume any rectangular shape. Our goal is to find the battleship by probing at least one of its squares. In this paper we describe a deterministic strategy for this problem which is guaranteed to locate the battleship in at most c 1 M/K probes, where c 1 ≈︁ 3.065.