On reporting the L1 L 1 metric closest pair in a query rectangle
In this work, we consider the problem of finding the closest pair (in L1 L 1 metric) of points in an orthogonal query rectangle. Given a set of n  static points on a UU U  U grid, we preprocess these points into a data structure of size O ( m f ( m ) log 2 m ) that can be queried in time O ( ( g ( m ) + log log m ) log 3 m ) , for m = O ( n log U ) and (i) f(m)=O(1) f ( m ) = O ( 1 ) and g ( m ) = O ( log ? m ) ; (ii) f ( m ) = O ( log log m ) and g ( m ) = O ( log log m ) ; (iii) f ( m ) = O ( log ? m ) and g(m)=O(1) g ( m ) = O ( 1 ) . Here ? : 0<?<1 0 < ? < 1 is a small but arbitrary constant.
closest pair computational geometry range queries manhattan metric