3
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Yes. Even for half-space queries we do not know how to do anything better, and it seems unlikely that one could do better. $\endgroup$ – Sariel Har-Peled Oct 4 '15 at 16:50
  • 1
    $\begingroup$ 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 $\endgroup$ – Sariel Har-Peled Oct 5 '15 at 2:16
  • $\begingroup$ 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. $\endgroup$ – Sayan Bandyapadhyay Oct 5 '15 at 4:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.