Fast Algorithms for 3-D Dominance Reporting and Counting
dc.contributor.author | Shi, Qingmin | en_US |
dc.contributor.author | JaJa, Joseph | en_US |
dc.date.accessioned | 2004-05-31T23:24:50Z | |
dc.date.available | 2004-05-31T23:24:50Z | |
dc.date.created | 2003-01 | en_US |
dc.date.issued | 2003-02-05 | en_US |
dc.description.abstract | We present in this paper fast algorithms for the 3-D dominance reporting and counting problems, and generalize the results to the d-dimensional case. Our 3-D dominance reporting algorithm achieves $O(\log n/\log\log n +f)$ query time using $O(n\log^{\epsilon}n)$ space, where $f$ is the number of points satisfying the query and $\epsilon>0$ is an arbitrary small constant. For the 3-D dominance counting problem (which is equivalent to the 3-D range counting problem), our algorithm runs in $O((\log n/\log\log n)^2)$ time using $O(nlog^{1+\epsilon}n/\log\log n)$ space. Also UMIACS-TR-2003-06 | en_US |
dc.format.extent | 191241 bytes | |
dc.format.mimetype | application/postscript | |
dc.identifier.uri | http://hdl.handle.net/1903/1253 | |
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-4437 | en_US |
dc.relation.ispartofseries | UMIACS; UMIACS-TR-2003-06 | en_US |
dc.title | Fast Algorithms for 3-D Dominance Reporting and Counting | en_US |
dc.type | Technical Report | en_US |