Data Structures Weiss 9.38

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.