Approximate Geometric Queries (using Balanced Aspect Ratio Trees)

geometric queries using data structures which preserve aspect
ratio bounds of the node-regions. In general, solving geometric
range queries (especially in higher-dimensions) is fairly difficult
and time consuming (roughly O(n^{1-1/d}) time). However, using
approximate techniques we can perform queries in O(log n) time
where the dependency on the dimension is placed on the approximation
factor (epsilon). The same holds for nearest neighbor queries.

This first lecture describes the "motivation" behind balanced
aspect ratio trees by discussing the various proofs (and simple
algorithms) behind solving approximate queries. We follow this
lecture on Tuesday with details on how balanced aspect ratio trees
are constructed.