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?
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