Linear space adaptive data structures for planar range reporting

Let S be a set of n points on an n×n integer grid. The maximal layer of S is a set of points in S that are not dominated by any other point in S. Considering Q as an axes-parallel query rectangle, we design an adaptive space efficient data structure using layers of maxima (iterative maximal layers)...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2016-05, Vol.116 (5), p.361-366
Main Authors: Das, Ananda Swarup, Gupta, Prosenjit
Format: Article
Language:English
Subjects:
Adaptive structures
Algorithms
Analysis of algorithms
Computational geometry
Computer science
Constants
Data analysis
Data processing
Data structures
Integer programming
Iterative methods
Layers of maxima
Linear space data structures
Maxima
Queries
Query processing
Range aggregate queries
Range minima queries
Rectangles
Reporting
Studies
Topology
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let S be a set of n points on an n×n integer grid. The maximal layer of S is a set of points in S that are not dominated by any other point in S. Considering Q as an axes-parallel query rectangle, we design an adaptive space efficient data structure using layers of maxima (iterative maximal layers) for reporting the points in Q∩S. Our data structure needs linear space and can be queried in time O(logε⁡n+Alogε⁡n+k). Here A is the number of layers of maxima with points in the query rectangle, k is the size of the output and ε is a small arbitrary constant in the range of (0,1). Also, A≤k. In the worst case, the query time of our data structure is O(klogε⁡n+k). Our model of computation is the word RAM with size of each word being Θ(log⁡n).
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2016.01.001