The ellipsoid method as a lion hunt in the Sahara

From Grötschel, Lovász, and Schrijver’s Geometric Algorithms and Combinatorial Optimization:

Recall the well-known method of catching a lion in the Sahara. It works as follows. Fence in the Sahara, and split it into two parts; check which part does not contain the lion, fence the other part in, and continue. After a finite number of steps we will have caught the lion — if there was any — because the fenced-in zone will be so small that the lion cannot move anymore. Or we realize that the fenced-in zone is so small that it cannot contain any lion, i.e., there was no lion at all. In order to illustrate the ellipsoid method by this old hunter’s story we have to describe what our Sahara is, how we split it into two parts, how we fence these in, and when we can declare the lion caught or nonexistent.

For a pictorial explanation, see here.