What is the minimal space requirement for triangular range counting queries in plane if one wants to process each query in poly-logarithmic time?
In [Goswami et al, 2004] they preprocess the points to create a data structure in $O(n^2)$ time and space achieving $O(\log n)$ query time for triangular range counting.
Is it the best known result till date?
References:
Partha P. Goswamia, Sandip Dasb, Subhas C. Nandy,
"Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment", 2004