Polygon Retrieval

Abstract

Given a set of N points on the plane and an arbitrary polygon, we consider how to efficiently find the subset of these points lying inside this polygon. A data structure will be displayed that occupies $O(N)$ space and enables polygon retrieval to be performed in $O(N^{\log _6 4} )$ worst-case execution time. This is the best currently known worst-case complexity.