I was reading this paper by Shamos, M.I, on "Geometric Intersection Problems" (http://citeseerx.ist.psu.edu/viewdoc/download?doi= , and was trying to understand it's Theorem 6, which says " Whether any two of N convex k-gons intersect can be determined in O(N(k+log N log k)) time."

I was stucked on the point 3 (Inclusion and intersection tests), in which the author says that " When a polygon is inserted, it ,it must be tested against its immediate neighbors for inclusion or intersection. As we have seen before, each such test can be done in O(k) time. "

I do not understand how is that possible. Theorem 5 of the same paper states that determining an intersection of two k-gons takes O(k log k) time.

If the author is talking about something else, then I didn't get that.
Any help appreciated.


1 Answer 1


In the paper you reference, Theorem 5 is a claim about simple polygons, where Theorem 6 deals with convex polygons, which are a special kind of simple polygons.

The 'As we have seen before, ...' refers to this line: 'As we have seen before, each such test can be done in $O(k)$ time.$^8$', where $8$ references another paper.

However, even though I do not know why you are reading this paper, I'd advise against it. This paper is pretty old and the main result (the $n\log n$ segment intersection algorithm) has been both improved upon and better explained by other sources. If you did not have an introductory course on computational geometry or something similar, I advise you to look at a computational geometry /algorithmic geometry textbook or lecture notes first.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.