Good splitters for counting points in triangles
Jiřı́ Matoušek, Emo Welzl · 1989
A set A of n points in the plane has to be stored in such a way that for any query triangle t the number of points of A inside t can be computed efficiently. For this problem a solution is presented with Ο(√n log n) query time, Ο (n log n) space and Ο(n3/2 log n) preprocessing time. The constants in the asymptotic bounds are small, and the method is easy to implement.