Show simple item record

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

dc.contributor.authorShi, Qingminen_US
dc.contributor.authorJaJa, Josephen_US
dc.description.abstractWe 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.extent183448 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-4508en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-2003-77en_US
dc.titleAn O(n)-Space O(log n/log log n + f)-Query Time Algorithm for 3-D Dominance Reportingen_US
dc.typeTechnical Reporten_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

Files in this item


This item appears in the following Collection(s)

Show simple item record