2019-03-01
Partial Enclosure Range Searching
Publication
Publication
A new type of range searching problem, called the partial enclosure range searching problem, is introduced in this paper. Given a set of geometric objects S and a query region Q, our goal is to identify those objects in S which intersect the query region Q by at least a fixed proportion of their original size. Two variations of this problem are studied. In the first variation, the objects in S are axis-parallel line segments and the goal is to count the total number of members of S so that their intersection with Q is at least a given proportion of their size. Here, Q can be an axis-parallel rectangle or a parallelogram of arbitrary orientation. In the second variation, S is a polygon and Q is an axis-parallel rectangle. The problem is to report the area of the intersection between the polygon S and a query rectangle Q.
| Additional Metadata | |
|---|---|
| Keywords | computational geometry, data structure, Partial range search, simplex range searching |
| Persistent URL | dx.doi.org/10.1142/S0218195919500018 |
| Journal | International Journal of Computational Geometry and Applications |
| Citation |
Bint, G. (Gregory), Maheshwari, A, Smid, M, & Nandy, S.C. (Subhas C.). (2019). Partial Enclosure Range Searching. In International Journal of Computational Geometry and Applications (Vol. 29, pp. 73–93). doi:10.1142/S0218195919500018
|