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.
Efficient algorithm for finding how many times a point is inside the triangles formed by given points
-
0What makes you think that you can do better than testing all triangles? Anyway, what is the motivation here? – 2011-06-20
-
1@lhf Simple heuristics strongly indicate there is a much better solution than the brute force $O(n^3)$ algorithm of testing all triangles. For instance, any random pair of the $\mathbf{n}$ points determines two half planes, immediately ruling out all triangles formed by points on the half plane not containing $\mathbf{p}$, which should be approximately one-eighth of all triangles. A few iterations of this will (on the average) eliminate a huge fraction of all the triangles at a cost of just $O(n)$. – 2011-06-21
-
1I disagree with both of these comments. As @whuber points out, there are certainly better ways than testing all the triangles. However, whuber's approach is still $O(n^3)$, since the number of triangles containing $\mathbb p$ increases with $n^3$, so discarding non-containing ones in $O(n)$ doesn't help, you'd also have to count the containing ones more than one at a time. Also, you say the eliminated fraction would be huge, but successive iterations are correlated, so you won't be eliminating one eighth in each iteration, so it's not obvious how huge the fraction will get how fast. – 2011-06-21
-
0@joriki I agree with that assessment (and was aware of the problem that these heuristics do not necessarily lead to a reduction in asymptotic best-case performance, which is why I chose vague quantifiers like "few" and "huge fraction.") My point was only that it is *obvious* that one can do better than "testing all triangles." The algorithm you provide is an excellent way to go about it! – 2011-06-21
1 Answers
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'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.
-
1Nice, this is a really clever algorithm. – 2011-06-21
-
0I dont think that there is an algorithm with $O(n \log{(n)}$ worst case runningtime . a regular polygon with n vertices we can construct about $\frac{n^2}{2}$ triangles that contain the center: select $A$ vertex a, select the vertex $B$ that is almost diagonally. Almost each triangle formed by $A$, $B$ and a vertext $C$ choosen from the longer of the two parts of the circumference divided by $A$ and $B$ contains the center. – 2011-06-21
-
1@miracle173: The task is to count the triangles, not to enumerate them. As I wrote in my comment under the question, there are actually $O(n^3)$ triangles containing $\mathbb p$ (under mild assumptions about the distributions of points); that doesn't prevent us from counting them in $O(n\log n)$ time. Regarding "worst case": There are no random elements in my algorithm; sorting and binary search can both be done in worst-case $O(n\log n)$ time. – 2011-06-21
-
1@miracle173: By the way, for a regular $n$-gon, too, there are $O(n^3)$ triangles containing the centre. – 2011-06-21
-
0@joriki: you are right. Should such a wrong comment be deleted? – 2011-06-23
-
0@miracle173: Good question -- I've wondered about that, too. As a rule, I'd say it makes sense to delete a comment if it's unlikely that someone will profit from reading it (or the reply), e.g. if it's a mistake that others are unlikely to make -- but who knows which mistakes others are likely to make? :-) – 2011-06-23
-
0after furher simplification one gets $$\frac{(2n-1)n(n-1)}{12}-\frac{\sum_{i=1}^{n}m_i^2}{2}$$ because the terms linear in $m_i$ can be summed up, – 2011-06-25