Running time for Testing Polygonal Neighbours for Intersection or Inclusion I was reading this  paper by Shamos, M.I, on "Geometric Intersection Problems" (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.366.9983&amp;rep=rep1&amp;type=pdf) , 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.
Thanks.
Moon
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.