1

We can solve the problem of segment intersection in 2D in O(nlgn) time. In this problem, we are given a set of line segments and we have to see if there is an intersection or not. Now her's a problem from CLRS.

Ques. Professor Charon has a set of n sticks, which are lying on top of each other in some configuration. Each stick is specified by its endpoints, and each endpoint is an ordered triple giving its (x, y, z) coordinates. No stick is vertical. He wishes to pick up all the sticks, one at a time, subject to the condition that he may pick up a stick only if there is no other stick on top of it. a. Give a procedure that takes two sticks a and b and reports whether a is above, below, or unrelated to b. b. Describe an efficient algorithm that determines whether it is possible to pick up all the sticks, and if so, provides a legal sequence of stick pickups to do so.

I find it is an extension of the segment intersection in 3D. In 2D, the sweep line moves in "y" and the array is sorted according to the "x" coordinate. I think in 3D, the sweep line should move in "z" dimension but m not sure how to sort now, since I have to take care of both "x" & "y".

If we somehow figure it out, I guess, if there is an intersection, then for part (b), its not possible to pick all the sticks.

Am I going in the right direction??

4

1 回答 1

3

可以使用 2D 中的线段相交来解决此问题。

检查一个段高于另一个段与检查 XY 投影中的交叉点相同，如果它们相交，则比较每个段上交叉点的 Z 坐标。例如，对于线段a=((0,0,0), (2,2,2))和b=((0,2,3), (2,0,5))，XY 上的投影是((0,0), (2,2))和((0,2), (2,0))。二维交点为， for中的(1,1)Z 值为1，for中的 Z 值为4。即在 上方。(1,1)abba

因此，使用 2D 中的段相交来查找哪些段是相关的。要查找删除段的顺序，请使用拓扑排序。

于 2013-11-13T10:03:55.383 回答