Efficient algorithm for transversal of d
✍
Francis Y.L. Chin; Fu Lee Wang
📂
Article
📅
2002
🏛
Elsevier Science
🌐
English
⚖ 103 KB
Given a set S of n disjoint convex polygons {P i | 1 i n} in a plane, each with k i vertices, the transversal problem is to determine whether there exists a straight line that goes through every polygon in S. We show that the transversal problem can be solved in O(N + n log n) time, where N = n i=1