Running time for Testing Polygonal Neighbours for Intersection or Inclusion
-
04-11-2019 - |
문제
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&rep=rep1&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
올바른 솔루션이 없습니다