Can one count the number of n points in m triangles in less than O(nm)?

We have n points given as $$(x,y)$$ coordinates and m triangles given as triples of $$(x,y)$$ coordinates, and want to count the number of times that one of the points is inside one of the triangles. The triangles may overlap so each point may be counted multiple times.

The naive way is to check each pair of a point and a triangle and count +1 if the point is inside the triangle. Is it possible to do it more efficiently than $$O(nm)$$?

• Off the top of my head, a kd-tree might be able to reduce one of the linear factors to a log factor Mar 8, 2019 at 22:57
– D.W.
Mar 9, 2019 at 6:50
• Thanks D.W. That one works only for non-overlapping triangles. Do you know how to extend it to overlapping triangles? Mar 10, 2019 at 16:57
• This is a difficult problem, because the count could be nm if the triangles overlap and each point is inside each of the triangles. I'm asking for an algorithm that nevertheless calculates the count in less than O(nm)... Mar 10, 2019 at 17:12

Pragmatic solution that's easy to implement

If you care more about a pragmatic solution that will likely work well enough in practice in most cases, and is easy to code, I would suggest storing each point in a quadtree. Then, for each triangle $$T$$, recursively search the quadtree to find all points within the triangle $$T$$. (This recursive search is pretty easy; at a node that represents a split of the space, check whether the triangle intersects the rectangular regions corresponding to the node's two children, and recurse on whichever node(s) it intersects.)

I don't know of any reason to think that the worst-case asymptotic running time will be better $$O(nm)$$ (e.g., it might perform poorly if you have many long, skinny, diagonal triangles), but it might work well in practice in many cases.

Sweepline algorithm

Alternatively, you could use a sweepline algorithm, similar to the Bentley-Ottman algorithm for detecting intersections among line segments. Unfortunately, it seems it might take quadratic time in the worst case.

Each triangle is defined by three line segments, so build the Bentley-Ottman data structures from these line segments. Also, you'll have an interval tree; for each triangle, it stores the interval of $$y$$-values that are obtained by intersecting that triangle with the current sweepline. Each point and each vertex of any triangle triggers an event when the sweepline hits that point or vertex. When you hit a point $$p$$, you can quickly count the number of triangles it is contained in: check the interval tree to see how many intervals in the tree contain it.

Each operation can be done in $$O(\log(n+m))$$ time. Unfortunately, there could be as many as $$O(n+m^2)$$ events (since there can be $$O(m^2)$$ intersections among the line segments), so in the worst case the total running time could be as bad as $$O((n+m^2)\log(n+m))$$. If you care only about typical running time, this might often do a lot better than that, as the number of intersections among the triangles might often be as little as $$O(m)$$, which would lead to a $$O((n+m)\log(n+m))$$ running time; but that's not guaranteed, and there exist inputs where it is much slower.

• Thanks a lot. I don't fully understand the second solution. Can't there be O(m^2) intersections? Also, the final count can be nm so to do better the algoritm needs to count multiple point-triangle containments at the same time. Mar 9, 2019 at 12:10
• @Jules, oh gosh, you're absolutely right. I missed that. Thank you for that correction.
– D.W.
Mar 9, 2019 at 19:58