An efficient range search algorithm for visualizing extrema of volume data

A fast range search algorithm for visualizing extrema of d-dimensional volume data in real time as the user interactively moves the query range is presented. The algorithm is based on an efficient data structure, called index heap, which needs only O(N/log N) space and O(d2/sup d/N) preprocessing time to be set up, where N is the size of the d-dimensional data volume. The algorithm can answer an extremum query in O(4/sup d/) expected time, and its worst-case time complexity is O(2/sup d/ log N) per query. For dimensions two and three, the range search for extrema is effected in average O(1) time per query independently of the size of query range. Unlike previous range query algorithms in the computational geometry literature, the proposed algorithm is very simple and can be easily implemented.<>