Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Range Aggregate Maximal Points in the Plane
verfasst von : Ananda Swarup Das, Prosenjit Gupta, Anil Kishore Kalavagattu, Jatin Agarwal, Kannan Srinathan, Kishore Kothapalli
Erschienen in: WALCOM: Algorithms and Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this work, we study the problem of reporting and counting maximal points in a query rectangle for a set of
n
integer points that lie on an
n
×
n
grid. A point is said to be maximal inside a query rectangle if it is not dominated by any other point inside the query rectangle. Our model of computation is unit-cost RAM model with word size of
O
(log
n
) bits. For the reporting version of the problem, we present a data structure of size
$O(n\frac{\log n}{\log\log n})$
words and support querying in
$O(\frac{\log n}{\log\log n}+k)$
time where
k
is the size of the output. For the counting version, we present a data structure of size
$O(n\frac{\log^{2} n}{\log\log n})$
words which supports querying in
$O(\frac{\log^{\frac{3}{2}}n} {\log\log n})$
. Both the data structures are static in nature. The reporting version of the problem has been studied in [1] and [5]. To the best of our knowledge, this is the first sub-logarithmic result for the reporting version and the first work for the counting version of the problem.