Efficient algorithm for finding how many times a point is inside the triangles formed by given points

Question

Given n 2D points and a special point p, what would be the best way to find how many times p is inside among those $^nC_3$ triangles formed by the n points.

Answer 1

Here's an algorithm in $O(n\log n)$ time and $O(n)$ space; I doubt you can do any better than that.

I'll assume general position, i.e., $\mathbb p$ isn't on the line through any two of the $n$ points. In the following, angles are normalized to some interval of length $2\pi$, say, $[0,2\pi)$, and differences between them are normalized to $(-\pi,\pi)$ by adding or subtracting $2\pi$ if necessary.

Calculate and order the angles under which the $n$ points appear from $\mathbb p$; this takes $O(n\log n)$ time. The number of triangles containing $\mathbb p$ is one third of the number of ordered triples of angles such that the difference between the angles is positive for all three pairs of (cyclically) successive angles. (It can't be zero or $\pi$ because of the assumption of general position.)

To count the number of such triples, assign indices to the angles according to their order, and for each angle $\alpha_i$ with index $i$ determine the number $m_i$ of indices $j$ such that $\alpha_j-\alpha_i$ is positive. This can be done in $O(n\log n)$ time by performing a binary search for the opposite angle $\alpha_i+\pi$.

Now iterate over $i$, counting the number of ordered triples with first element $\alpha_i$ that fulfill the above condition. For each second element $\alpha_j$ with positive $\alpha_j-\alpha_i$, the number of such triples is the number of third elements $\alpha_k$ such that both $\alpha_k-\alpha_j$ and $\alpha_i-\alpha_k$ are positive. This is the overlap between the $m_j$ angles for which $\alpha_k-\alpha_j$ is positive and the $n-m_i-1$ angles for which $\alpha_k-\alpha_i$ is negative. This can be written as $m_j+(n-m_i-1)-(n-d_{ij}-1)=m_j+d_{ij}-m_i$, where $d_{ij}$ is the cyclical distance from $i$ to $j$. (A circle diagram containing those three terms might aid understanding.)

The term $m_i$ is independent of $j$, so summing it over $j$ just gives $m_i^2$. The term $d_{ij}$ is also readily summed over $j$; the sum is $m_i(m_i+1)/2$, so these terms together contribute $-m_i(m_i-1)/2$. The sum over $m_j$ can be calculated in constant time by precalculating the sums $\sum_{j<i}m_j$; then the sum over $m_j$ for $\alpha_j-\alpha_i$ positive is just the cyclical difference between two such sums, one with index $i$ and the other with the "opposite" index that was already determined by binary search to calculate $m_i$ above.

I've skipped over some of the technical details, but I hope it's clear how all the steps can be carried out in $O(n\log n)$ time. (Clearly the data structures used only use $O(n)$ space.)

[Edit:] There was an error in the original calculation. Incidentally, the correct calculation is slightly simpler. It also allows us to immediately derive the number of triangles in the case of a regular $n$-gon (with $n$ odd for general position): In this case, all $m_i$ are equal, so $m_j$ and $m_i$ cancel, and the result is just $1/3$ of the sum of $d_{ij}$ over $i$ and $j$, which is $nm(m+1)/2$. Here $m$ is the common value of the $m_i$, which is $(n-1)/2$; the end result is $n(n^2-1)/24$ triangles.