1. Graph Algorithms Unmanned Aerial Vehicles (UAVs), commonly known as drones, a
ID: 3889095 • Letter: 1
Question
1. Graph Algorithms
Unmanned Aerial Vehicles (UAVs), commonly known as drones, are starting to be used for high resolution and 3D mapping1. A group of ecologists have decided to use a (small) UAV to map out their study area, down to every tree. Unfortunately, it is hard to tell from the resulting image data the total number of species of trees in the area since many look similar.2 Suppose there are n trees in the area and let us assume for simplicity that there are only two dierent species, say Acacia and Bactris. Believe it or not, it is very hard to tell by looking at a tree by itself which kind it is. However, it is much easier to tell whether two trees are the same species or not. So the scientists do the following. For each pair of 3D tree images i and j the scientists look at them side by side and decide whether they are the “same” species or “dierent”. They also have the option of not giving an opinion and just leave the pair without a decision.
So now the scientists have the collection of n trees, as well as a collection of m decisions (either “same” or “dierent”) for the pairs for which some decision was made. They would like to know whether this data is self-consistent. That is, we will say that m decisions are consistent if it is possible to reliably label each tree either Acacia or Bactris in such a way that for each “same” pair (i, j) the trees i and j indeed have the same label, while for each “dierent” pair (i, j) the trees i and j have dierent labels. Give an algorithm with running time O(m+n) that determines whether the m decisions are consistent. Don’t forget to prove its correctness and termination.
Extra Credit: Will your algorithm work if there are more than two species, say three (with Cecropia)? If it does, give a proof of correctness. If not, give a counter-example.
Explanation / Answer
Low-elevation surveys with small aerial drones (micro–unmanned aerial vehicles [UAVs]) may be used for a wide variety of applications in plant ecology, including mapping vegetation over small- to medium-sized regions. We provide an overview of methods and procedures for conducting surveys and illustrate some of these applications.
Methods:
Aerial images were obtained by flying a small drone along transects over the area of interest. Images were used to create a composite image (orthomosaic) and a digital surface model (DSM). Vegetation classification was conducted manually and using an automated routine. Coverage of an individual species was estimated from aerial images.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.