This year again, the heatwave has ravaged the university campus. Fortunately, the trees and green spaces have helped users endure the temperature. To improve the situation, the university would like to plant trees so that all utilized areas are covered by their shade. However, trees cannot be planted in concrete areas and must be replaced by umbrellas, which are less effective. Concrete areas reflect heat, limiting the spread of coolness.
The project will be carried out in several stages:
About the organization:
You are presented with the following problems: How can trees be placed so that all utilized areas of the campus (sidewalks, etc.) are covered by shade? What is the minimum number of trees needed to cover these areas?
In a second phase, you will consider additional problems with umbrellas and the variation of the covered distance depending on the terrain.
You may also propose your own variants of the problems, justifying why they are relevant.
You will present your results graphically to facilitate understanding of your proposals.
To carry out the project, you will need the cartographic data of the campus. This data can be retrieved via OpenStreetMap, for example by using Overpass queries. You can also use other open sources that you find. OSMnx may also be useful if you choose to do your project in Python.
Each group will prepare a mini-presentation of the modeling. The chosen tools for the implementation will also be presented.
dominating_set(graph G, partial dominant S, integer k)
if k = 0 :
test if S is a dominant set
else :
u <- vertex of minimum degree among the vertices not dominated by S
for all v in N[u] :
dominating_set(G, S U {v}, k-1)
Remember to start a report for the upcoming submissions.
You have to write a report covering the following points: