An O(n)-Space O(log n/log log n + f)-Query Time Algorithm for 3-D Dominance Reporting
| dc.contributor.author | Shi, Qingmin | en_US |
| dc.contributor.author | JaJa, Joseph | en_US |
| dc.date.accessioned | 2004-05-31T23:30:58Z | |
| dc.date.available | 2004-05-31T23:30:58Z | |
| dc.date.created | 2003-07 | en_US |
| dc.date.issued | 2003-08-01 | en_US |
| dc.description.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) | en_US |
| dc.format.extent | 183448 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/1301 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-4508 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-2003-77 | en_US |
| dc.title | An O(n)-Space O(log n/log log n + f)-Query Time Algorithm for 3-D Dominance Reporting | en_US |
| dc.type | Technical Report | en_US |