On reporting the L1L1 metric closest pair in a query rectangle

In this work, we consider the problem of finding the closest pair (in L1L1 metric) of points in an orthogonal query rectangle. Given a set of n   static points on a U×UU×U grid, we preprocess these points into a data structure of size O(mf(m)log2m) that can be queried in time O((g(m)+loglogm)log3m), for m=O(nlogU) and (i) f(m)=O(1)f(m)=O(1) and g(m)=O(logεm); (ii) f(m)=O(loglogm) and g(m)=O(loglogm); (iii) f(m)=O(logεm) and g(m)=O(1)g(m)=O(1). Here ε  : 0<ε<10<ε<1 is a small but arbitrary constant.