Polygon Retrieval
- 1 February 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 11 (1) , 149-165
- https://doi.org/10.1137/0211012
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.
Keywords
This publication has 16 references indexed in Scilit:
- A Lower Bound on the Complexity of Orthogonal Range QueriesJournal of the ACM, 1981
- Lower Bounds on the Complexity of Some Optimal Data StructuresSIAM Journal on Computing, 1981
- Decomposable searching problems I. Static-to-dynamic transformationJournal of Algorithms, 1980
- Multidimensional divide-and-conquerCommunications of the ACM, 1980
- Efficient worst-case data structures for range searchingActa Informatica, 1980
- Decomposing a polygon into its convex partsPublished by Association for Computing Machinery (ACM) ,1979
- Multidimensional Searching ProblemsSIAM Journal on Computing, 1976
- Multidimensional binary search trees used for associative searchingCommunications of the ACM, 1975
- Analysis of range searches in quad treesInformation Processing Letters, 1975
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974