<p>What is the minimal space requirement for 
triangular range counting queries in plane 
if one wants to process each query in poly-logarithmic time?</p>

<p>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.</p>

<p>Is it the best known result till date?</p>

<hr>

<p>References:
Partha P. Goswamia, Sandip Dasb, Subhas C. Nandy,<br>
"<a href="http://www.sciencedirect.com/science/article/pii/S092577210400029X" rel="nofollow">Triangular range counting query in 2D and its application in finding k nearest neighbors of a line segment</a>", 2004</p>

CC BY-SA 3.0
2015-10-04T16:50:12.630Z
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
CC BY-SA 3.0
2015-10-05T02:16:27.280Z
Na, I am too lazy to figure out the right refs. But the following would have the right refs somewhere:
http://jeffe.cs.illinois.edu/pubs/pdf/survey-tr.pdf
Sariel Har-Peled
CC BY-SA 3.0
2015-10-05T04:34:02.087Z
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
<ds.data-structures><computational-geometry><range-searching>
Triangular range counting query in poly-logarithmic time
Sayan Bandyapadhyay
# Triangular range counting query in poly-logarithmic time

(Asked by: username_0 on 2015-10-04)

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](http://www.sciencedirect.com/science/article/pii/S092577210400029X)", 2004

**Tags:** ds.data-structures, computational-geometry, range-searching
> **Comments:**
> **username_1**: Yes.  Even for half-space  queries we do not know how to do anything better, and it seems unlikely that one could do better.  
> **username_1**: Na, I am too lazy to figure out the right refs. But the following would have the right refs somewhere: http://jeffe.cs.illinois.edu/pubs/pdf/survey-tr.pdf  
> **username_0**: 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.  

---

## 0 answers

