7
$\begingroup$

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.

  • 0
    What 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
  • 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.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 1