Fast Algorithms for 3-D Dominance Reporting and Counting

dc.contributor.authorShi, Qingminen_US
dc.contributor.authorJaJa, Josephen_US
dc.date.accessioned2004-05-31T23:24:50Z
dc.date.available2004-05-31T23:24:50Z
dc.date.created2003-01en_US
dc.date.issued2003-02-05en_US
dc.description.abstractWe 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-06en_US
dc.format.extent191241 bytes
dc.format.mimetypeapplication/postscript
dc.identifier.urihttp://hdl.handle.net/1903/1253
dc.language.isoen_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-4437en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-2003-06en_US
dc.titleFast Algorithms for 3-D Dominance Reporting and Countingen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
CS-TR-4437.ps
Size:
186.76 KB
Format:
Postscript Files
Loading...
Thumbnail Image
Name:
CS-TR-4437.pdf
Size:
180.32 KB
Format:
Adobe Portable Document Format
Description:
Auto-generated copy of CS-TR-4437.ps