Dominance made simple
In this note we show that it is extremely easy to answer dominance queries in three dimensions using only range minima routine (and a binary tree). The algorithm after preprocessing takes O(logn + S) time,where S is the size of output (after O(n log n) time for pre-processing). The algorithm can also be used to answer 5-sided range queries, in same time bounds. (C) 2008 Elsevier B.V. All rights reserved.
dominance query algorithms range query orthogonal range query computational geometry parallel algorithms