You are given a set of N sticks, which are lying on top of each other in some co

Question

You are given a set of N sticks, which are lying on top of each other in some configuration. Each stick is specified by its two endpoints; each endpoint is an ordered triple giving its x, y, and z coordinates; no stick is vertical. A stick may be picked up only if there is no stick on top of it.

a. Explain how to write a routine that takes two sticks a and b and reports whether a is above, below, or unrelated to b. (This has nothing to do with graph theory.)

My solution: Compute ranges of the two sticks on x and y axes. If the intersection of x ranges of a and b or the intersection of y ranges of a and b are zero, two sticks are not in the same place. If both are not zero, then calculate the point at which two sticks cross(intersection of the two lines in the x-y planes) and the stick with the higher z-value at that point is on top.

b. Give an algorithm that determines whether it is possible to pick up all the sticks, and if so, provides a sequence of stick pickups that accomplishes this.

I do not know what algorithm I should utilize.

for question A, Please let me know if it is not correct or if it is vauge.

for question B, please let me know which algorithm could be appropriate.

Explanation / Answer

algorithm to find whether a is above or below or un related to b:1) in all the coordinates of a, b make z=02) then you will get projections of the sticks a and b on x-y plane3) a) if both the sticks are intersecting in x-y plane then a is above or below bB) if both sticks are not intersecting then a is unrelated to b4) if both are intersecting (case 3a) the find the intersection point in x-y plane5) find the z co-ordinates of a, b at the intersection point6) if z co-ordinate of a is more than b at intersection point then a above bb) else b is above afor ex: segments a=((0,0,0), (2,2,2)) and b=((0,2,3), (2,0,5)),projection on X-Y is ((0,0), (2,2))and ((0,2), (2,0)). intersection is (1,1),Z value in (1,1) for a is 1, and for b is 4.That means b is above a. Algorithm to determine wehther it is possible to pickup all the sticks1) create a graph of n verices (1 vertex for each node)2) take each possible pair of sticks and apply the above algorithm3) for each pair a, ba) if a is above b , then add a directed edge from a to bif b is above a then add a directed edge from b to aif a is unrelated to b , do nothing4) find for cycles if cycle is there , that means it is not possible to pick all the sticks5) if there are no cycles then find the topological order of this graph6) that is the order in which you have to remove sticks

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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