Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What makes you think that you can do better than testing all triangles? Anyway, what is the motivation here? –  lhf Jun 20 '11 at 22:50
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)$. –  whuber Jun 21 '11 at 3:58
1  
I 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. –  joriki Jun 21 '11 at 4:59
    
@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! –  whuber Jun 21 '11 at 14:07
add comment

1 Answer

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.

share|improve this answer
1  
Nice, this is a really clever algorithm. –  ShreevatsaR Jun 21 '11 at 6:54
    
I 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. –  miracle173 Jun 21 '11 at 7:45
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. –  joriki Jun 21 '11 at 8:01
1  
@miracle173: By the way, for a regular $n$-gon, too, there are $O(n^3)$ triangles containing the centre. –  joriki Jun 21 '11 at 8:15
    
@joriki: you are right. Should such a wrong comment be deleted? –  miracle173 Jun 23 '11 at 22:25
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.