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

Graph coloring algorithm -

The question is basically to check whether we can color the graph with two colors.

If the label of the pair is same then both the elements have same color.

If the label of the pair is different then both the trees have different color.

We can solve the above problem by declaring every tree as a node of the graph .

If the label of the pair is different then add an edge between the corresponding two nodes. Do this for all the edges and get the graph .

Now select one node and do the dfs traversal of the graph and assign different color to each adjacent node. If we find the back edge in dfs and if the contradiction occurs then the data is not consistent. Else data is self consistent.

This is not possible in case of three species because to color the graph with three colors is NP hard problem .

example n = 5

1-4, 2-4, 3-4 , 1-2 , 2-3

start dfs from 1

edge traversal order 1-2, 2-3, 3-4 . Here no cotradiction occurs, but actually we cant color this graph by using three colors.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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