I/O-efficient Triangular Range Search and Its Application

by Gautam K. Das

We consider a special type of triangular range search for a planar  
point set S in the I/O-model. Here, two sides of the query triangle  
are parallel to coordinate axes (x- and y-axis). We call such a  
triangle an axis parallel triangle. For the axis parallel triangular  
range search problem, we propose an efficient data structure in I/O  
model setup. We also consider the application of this data structure  
and query algorithm to oriented rectangular range search.

Joint work with Bradford G. Nickerson (UNB Faculty of Computer Science)