Computing Point Enclosures
- 1 January 1982
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-31 (1) , 22-29
- https://doi.org/10.1109/tc.1982.1675881
Abstract
Given a set of n rectangles in the plane, the point enclosure query is the question to determine for any point p which rectangles of the set it is contained in. It is the "dual" of the well-known range query in computational geometry. It is shown that the point enclosure query in the plane can be answered in 0(log n + k) time, where k is the number of rectangles reported. The solution makes use of a new data structure, called the S-tree. The data structure can be generalized to obtain an efficient algorithm for the point enclosure problem in d-dimensional space d ≥ 2.Keywords
This publication has 21 references indexed in Scilit:
- Rectilinear line segment intersection, layered segment trees, and dynamizationJournal of Algorithms, 1982
- A Lower Bound on the Complexity of Orthogonal Range QueriesJournal of the ACM, 1981
- Dynamization of decomposable searching problems yielding good worst-case boundsPublished by Springer Nature ,1981
- The rectangle intersection problem revisitedBIT Numerical Mathematics, 1980
- Quintary treesACM Transactions on Database Systems, 1980
- Space and time optimal algorithms for a class of rectangle intersection problemsInformation Sciences, 1980
- Multidimensional divide-and-conquerCommunications of the ACM, 1980
- Dynamization of decomposable searching problemsInformation Processing Letters, 1980
- Data Structures for Range SearchingACM Computing Surveys, 1979
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975