Dive Into Algorithms

7 Geometry

We humans have a deep, intuitive grasp of geometry. Every time we maneuver a couch through a hallway, draw a picture in Pictionary, or judge how far away another car on the highway is, we’re engaging in some kind of geometric reasoning, often depending on algorithms that we’ve unconsciously mastered. By now, you won’t be surprised to learn that advanced geometry is a natural fit for algorithmic reasoning.

In this chapter, we’ll use a geometric algorithm to solve the postmaster problem. We’ll begin with a description of the problem and see how we can solve it using Voronoi diagrams. The rest of the chapter explains how to algorithmically ...