Largest empty shapes

Finding the largest empty shapes

This post is about finding empty regions (square, rectangle, or circle) in a (large) collection of given points. These are interesting little optimization problems.

Data

I generated \(n=100\) data points \((x_i,y_i), i=1,\dots,n\) drawn from a uniform distribution \[\begin{align}&x_i \sim U(0,10) \\ & y_i \sim U(0,10)\end{align} \] 

It is always a good idea to have a careful look at the data. I.e., print and plot it (for very large datasets, print or plot a subset), and collect some elementary statistics (min, max, average, etc.). In practical modeling, it is surprising how many problems arise from simple data errors.