Unmanned Aerial Vehicles (UAVs), commonly known as drones, are starting to be us

Question

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 different 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 “different”. 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 “different”) 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 “different” pair (i, j) the trees i and j have different 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. Note that the input consists of the number of trees, n, and a list of m decisions for some pairs of trees. For example, n = 4, and (1, 2) same, (1, 3) different, (2, 4) same. 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

Since there are only two species, each tree can be labelled either same i.e 0 or different i.e 1. Classification can be done by successively comparing each tree with its adjecent tree by arrangng them in matrix form.

Interpretation of Self consistency

For given m decision for pair, where number of trees are n, self consistency can be proved if all element of matrix A where trees are arranged in two dimentional matrix form can be labelled either 0 i.e same or 1 i.e different. At end if we found any pair for which no decision is made, it can declare Data inconsistent. This is nothing but calcultaing the trasitive closure of pairs represented by m decisions.

Algorithm:

/* Algorithm to decide the Self consistentecy of M decision made over N trees */

Input:

Matrix of Size N X N containing m marked decisions. Pair for which no decision are made marked 9. for same pair 0 and for different .

Algorithm:

  for (k = 0; k < N; k++)

  for (i = 0; i < N; i++)

for (j = 0; j < N; j++)

A[i][j] = A[i][j] || (A[i][k] && A[k][j]); // If i is same as j and j is same as k than i is same as k

int sum=0;

  for (k = 0; k < N; k++)

  for (i = 0; i < N; i++)

if A[i][j]==9

Declare inconsistent

Declare consistent 9 is not found.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.