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

Research output: Book/ReportReportResearch

421 Downloads (Pure)


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.
Original languageEnglish
PublisherDTU Wind Energy
Number of pages9
ISBN (Electronic)978-87-92896-19-3
Publication statusPublished - 2012
SeriesDTU Wind Energy E

Bibliographical note

Contract no: 11/02917; project no: 43087; Sponsor: Business Innovation Fund (www.fornyelsesfonden.dk)


  • DTU-Wind-Energy-E-0013(EN)


Dive into the research topics of 'A Greedy Algorithm for a Special Class of Geometric Set Covering Problems'. Together they form a unique fingerprint.

Cite this