A Greedy Algorithm for a Special Class of Geometric Set Covering Problems

We consider the problem of covering a set of given points in the plane by the smallest number of axis aligned squares of a given fixed size. This problem is of importance for computational fluid dynamics simulations of both onshore and offshore wind turbine parks. For this special case of a geometric set covering problem we propose a greedy type algorithm.

We also propose a linear mixed 0 – 1 formulation of the problem. For each problem instance this formulation is solved by a commercial branch-andcut solver and the results are used to validate the quality of the solution from the greedy algorithm. The greedy algorithm finds the minimum number of squares for all but one problem instances from a set of 26 representative real-world examples.