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.)

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.

Explanation / Answer

Algorithm to find whether a UN related to b:

1) In all the coordinates of a, b make z=0

2) Then you will get projections of the sticks a and b on x-y plane

3) A) if both the sticks are intersecting in x-y plane then a is above or below b

B) If both sticks are not intersecting then a is unrelated to b

4) If both are intersecting case 3a the find the intersection point in x-y plane

5) Find the z co-ordinates of a, b at the intersection point

6) If z co-ordinate of a is more than b at intersection point then a above b

b) Else b is above a

For example:

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 whther it is possible to pickup all the sticks

1) create a graph of n verices (1 vertex for each node)

2) take each possible pair of sticks and apply the above algorithm

3) for each pair a, b

a) if a is above b , then add a directed edge from a to b

if b is above a then add a directed edge from b to a

if a is unrelated to b , do nothing

4) find for cycles

if cycle is there , that means it is not possible to pick all the sticks

5) if there are no cycles then find the topological order of this graph

6) 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.