Abstract: General purpose spatial data structures like the k-d trees and quad trees are widely used to answer a variety of queries like range searches, proximity queries, and nearest-neighbor queries. They, however, do not have good bounds on worst case performance for either the exact or the approximate versions of these queries. Good bounds for the approximate versions exist if a tree has bounds on both the depth and the aspect ratio of the regions --- the aspect ratio is small if the region is "well rounded". We present Parameterized Balanced Aspect Ratio (PBAR) trees and show that they have the desired bounds. A PBAR tree can be constructed using any three given partitioning vectors and form regions that are convex; they are superior to other recently developed data structures that too have bounds on the depth and aspect ratio.
This talk is based on work done jointly with Breno De Medeiros and Michael Goodrich.