Problem: given a set of N non-superimposed convex polygons {S_i, i = 1..N} defined by their vertex coordinates (x, y) and a convex polygon P, also defined by their vertex coordinates, find all the polygons S_i what overlap with P. Suppose an algorithm to check if there is already an overlap of a pair of polygons.

Restrictions: We are allowed to perform O (N) operations on {S_i} without knowledge of P (initialization step). After that, given an arbitrary P, the algorithm should work in an approximate time of O (N record) when S consists of polygons of uniform size. Therefore, an algorithm that simply tests P against each S_i will be rejected.

Idea of solution: in the initialization, insert all the vertices of the polygons of {S_i} in a kd-tree K and associate each vertex with its associated polygon. Store the diameter dS of the largest polygon in {S_i}. Then, given a polygon P, calculate the diameter dP of P. Find all the vertices in K that are no farther from the maximum (dS, dP) / 2 (?) Of any vertex in P. Try P against the faces that contain the vertices in K.

Since the search on K is a register operation (N), then if N is large and dP is approximately equal to dS, the number of tests should be << N.

Any other solution idea? Google is not giving anything of value.

Similar to How to find, the polygons overlap, but with additional restrictions.