smurf2's blog

By smurf2, history, 7 months ago, In English,

What is the best algorithm for querying the number of points in a triangle? Given that there are n points and q queries.

  • Vote: I like it
  • +13
  • Vote: I do not like it

7 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Pick's theorem can help you, which count total integral point inside triangle

7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

You can break down a triangle query to a constant amount of "ray" queries; how many points are under a ray. Specifically let's break it to "prefix" rays — those which extend infinitely to the left.

If we sort the points according to x-axis, then the prefix ray queries become queries to count points under a line inside some prefix. Let's break the array to $$$\frac{N}{K}$$$ blocks of size $$$K$$$. For the tail of the prefix query (the cells which are not in a complete block), count normally in $$$\mathcal{O}(K)$$$. As for the blocks, you can do some precomputation described nicely here. You end up with $$$\mathcal{O}(\sqrt{N} \cdot polylog N)$$$ per query for an optimal choice for $$$K$$$ (the polylog depends on how you implement whichever approach is described in the linked post). This approach is probably not noticeably faster for acceptable values of $$$N, Q$$$, but at least it's sublinear.

Also, this works online, but if you allow yourself offline then you can do cuts on complexities, some shown in the linked post, and some can be done here to cut down memory a lot (build the structure per block on its own, and move to the next one using the same memory, for instance).