Point Enclosure Problem for Homothetic Polygons

12/03/2021
by   Waseem Akram, et al.
0

In this paper, we investigate the homothetic point enclosure problem: given a set S of n triangles with sides parallel to three fixed directions, find a data structure for S that can report all the triangles of S that contain a query point efficiently. The problem is "inverse" of the homothetic range search problem. We present an O(nlog n) space solution that supports the queries in O(log n + k) time, where k is the output size. The preprocessing time is O(nlog n). The same results also hold for homothetic polygons.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset