An O(n)-Space O(log n/log log n + f)-Query Time Algorithm for 3-D Dominance Reporting

Loading...
Thumbnail Image

Files

CS-TR-4508.ps (179.15 KB)
No. of downloads: 307
CS-TR-4508.pdf (190.2 KB)
No. of downloads: 749

Publication or External Link

Date

2003-08-01

Advisor

Citation

DRUM DOI

Abstract

We present a linear-space algorithm for handling the {\em three-dimensional dominance reporting problem}: given a set $S$ of $n$ three-dimensional points, design a data structure for $S$ so that the points in $S$ which dominate a given query point can be reported quickly. Under the variation of the RAM model introduced by Fredman and Willard~\cite{Fredman94}, our algorithm achieves $O(\log n/\log\log n+f)$ query time, where $f$ is the number of points reported. Extensions to higher dimensions are also reported. (UMIACS-TR-2003-77)

Notes

Rights