A Simple Algorithm

This section describes a simple shape discovery algorithm that requires at most 3n+1 probes to discover of polygon with n vertices. This algorithm is described in many steps. We will start by explaining the intuition that leads to the algorithm. We will then define the vocabulary and data structures used in the algorithm. The algorithm will then be described in details, after which we will analyze it and prove the upper bound of 3n+1 probes.

Shape Discovery

Intuition