For a set of sites in a plane, the convex hull of the sites is the smallest convex polygon which contains all of the sites.

The Largest Empty Circle problem is the problem of finding the largest circle centred within the convex hull whose interior does not contain any sites.

Because we could consider this as finding the optimal position to place a toxic waste dump (i.e. as far from the nearest towns as possible) this is sometimes called a Toxic Waste Dump Problem.

We solve the problem by drawing the Voronoi diagram for the sites.

Worked Example

The Voronoi diagram for the sites A(-2,1), B(-1,4), C(2,3) and D(2,-3) is shown below:

Find the largest empty circle for these sites.

Exercise

Answers