Game of Jack Straws
In the game of Jack Straws, a number of plastic or wooden "straws" are dumped on the table and players try to remove them onebyone without disturbing the other straws. In the question here, we are concerned with the following, related problem: First n straws are dumped on the table. Next, for every pair of straws, we want to determine if the straws are connected by a path of touching straws. In other words, given a list of the endpoints for n > 1 straws (as if they were dumped on a large piece of graph paper), determine all the pairs of straws that are connected. Note that touching is connecting, but also two straws can be connected indirectly via other connected straws. Give an algorithm to compute all the pairs of straws that are connected.
Here is some additional information that you can use:
As a basic step you need to determine whether two straws directly touch (intersect), i.e., whether straw ab with end points a and b intersects with straw cd (with end points c and d).
To get full credit also explain how the elementary step i) can be done. If you cannot find an algorithm for this step, assume an O(n 2 ) algorithm and explain how to find all pairs of straws that are connected.
Analyse and explain the worstcase computational complexity of your algorithm in terms of n.

Interview Candidate
 May 28th, 2015
 0
 3953
This Question is not yet answered!
Related Answered Questions
Related Open Questions
Game of Jack Straws
Here is some additional information that you can use:
As a basic step you need to determine whether two straws directly touch (intersect), i.e., whether straw ab with end points a and b intersects with straw cd (with end points c and d).
To get full credit also explain how the elementary step i) can be done. If you cannot find an algorithm for this step, assume an O(n 2 ) algorithm and explain how to find all pairs of straws that are connected.
Analyse and explain the worstcase computational complexity of your algorithm in terms of n.
This Question is not yet answered!
Related Answered Questions
Related Open Questions