# Triangular range counting query in poly-logarithmic time

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

• Yes. Even for half-space queries we do not know how to do anything better, and it seems unlikely that one could do better. – Sariel Har-Peled Oct 4 '15 at 16:50
• Na, I am too lazy to figure out the right refs. But the following would have the right refs somewhere: jeffe.cs.illinois.edu/pubs/pdf/survey-tr.pdf – Sariel Har-Peled Oct 5 '15 at 2:16
• I have seen this survey before. This is years old. I wonder if anything came up after that or even after the reference I mentioned, something which proves a lower bound. – Sayan Bandyapadhyay Oct 5 '15 at 4:34