Count acute triangles

Question

You're given coordinates (x,y) of N different points in plane. Count acute triangles formed with given points. Brute-force is simple, but it's complexity is binomial coefficient (n,3). Does anyone have faster idea?

Answer 1

Here is my solution:

Start with one point p1. Now, find the slopes of lines formed with the current point and all other points. Sort the points accordingly.

Consider the first point a1 in this array. Let the slope be denoted by m. Now, find the slope of the line that is perpendicular to this line.

m_p = tan-1 ( 90 + tan(m))

Perform a binary search for m_p in the array and take the index of that slope that is less than or equal to m_p. This gives the count of tuples which form acute angle in which two of the points are p1 and a1. Now, consider the next point in the array and do the same operation.

Repeat the above procedure for each and every point.

Time Complexity Analysis:

For sorting: O(NlogN)

For Binary Search: logN. Repeating this on every point in the array takes O(NlogN)

Repeating the above steps for each point takes:

O(N*NlogN) = O(N²logN)

EDIT:

I thought tan is increasing function in range (0,2*PI). Its better to find the angle each line makes with the positive x-axis and then sort them w.r.t these values. Now, consider for each point pi, the number of points between angle ai and ai+90. When you consider these points, the angle made at the Main point is always acute.

This will cover all the cases no matter what the angle is.

EDIT 2:

My solution is only half-correct. It only ensures that angle at the Main point is acute. But doesn't guarantee at the other two points.

What you need to do in addition to the above procedure is form another set of points (xi,yi) for each point. Where xi denotes the angle of the line between main point and x-axis and yi denotes the distance between the Main Point and the current one.

Construct a kd-tree with these new set of points. Now for each point ai, search in the kd-tree for those points whose angle lies between mi and mi+90, and whose distance lies between 0 and distance between ai and Main_Point.

This additional constraint forces the other two angles to be acute. I leave it as an exercise to resolve it.

Now the time complexity is: O(N²logN) in average case and O(N³) in the worst case(because of the kd-tree we are using).