Home
Scholarly Works
An efficient range search algorithm for...
Conference

An efficient range search algorithm for visualizing extrema of volume data

Abstract

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.<>

Authors

Wu X; Fang Y

Pagination

pp. 132-138

Publisher

Institute of Electrical and Electronics Engineers (IEEE)

Publication Date

January 1, 1992

DOI

10.1109/visual.1992.235216

Name of conference

Proceedings Visualization '92
View published work (Non-McMaster Users)

Contact the Experts team