Closest-Pair Queries in Fat Rectangles

Michiel Smid

Carleton University

Given a set $S$ of $n$ points in the plane, we want to answers queries of the type ``for a query rectangle $R$, report the closest pair among all points of $S$ that are inside $R$''. The currently best data structure for this problem has size $O(n \log^2 n)$ and query time $O(\log^2 n)$.

I will present a data structure of size $O(n \log n)$ that supports closest-pair queries in $O(\log n)$ time for fat query rectangles.

This is joint work with Sang Won Bae.