Optimal solutions for a class of point retrieval problems
Let P be a set of n points in the Euclidean plane and let C be a convex figure. We study the problem of preprocessing P so that for any query point q, the points of P in \(C+q\) can be retrieved efficiently. If constant time suffices for deciding the inclusion of a point in C, we then demonstrate the existence of an optimal solution: the algorithm requires O(n) space and \(O(k+\log n)\) time for a query with output size k. If C is a disk, the problem becomes the well-known fixed-radius neighbour problem, to which we thus provide the first known optimal solution.
- A note on Euclidean near neighbor searching in the plane
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- scientific article; zbMATH DE number 3473265 (Why is no real title available?)
- New Data Structures for Orthogonal Range Queries
- On the shape of a set of points in the plane
- Polygonal intersection searching
- A unified algorithm for finding maximum and minimum object enclosing rectangles and cuboids
- scientific article; zbMATH DE number 3911763 (Why is no real title available?)
- Point retrieval for polygons
- AN OPTIMAL CONSTRUCTION METHOD FOR GENERALIZED CONVEX LAYERS
- An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ3
- Linear space data structures for two types of range search
- Half-plane point retrieval queries with independent and dependent geometric uncertainties
- Dynamic unit-disk range reporting
This page was built for publication: Optimal solutions for a class of point retrieval problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1062772)
