CODEWITHSUNDEEP
algorithmperformancegeometry
Dogey Dog
Dogey Dog

Reputation: 23

Number of distinct triangle vertices

I was given the following question to solve:

Consider you are given N distinct points with both a positive x coordinate and positive y coordinate. For each coordinate you are to form a right triangle with two sides that connect the coordinate and the x-axis 45 degrees relative to the x-axis. Thus a right angle is formed at the intersection of both sides, and the hypotenuse of the triangle is on the x-axis. After you have created these triangles, find number of points out of the given N points in which none of the created triangles overlap with these points.

For example, let's say N = 3 and we are given the points : (4, 6), (7, 2), (2, 5)

Additional vertices for triangle of point (4,6) : (-2,6), (10,6)

Additional Vertices for trianlge of point (7,2) : (5,2), (9,2)

Additional Vertices for triangle of point (2,5) : (-3,5), (7,5)

In this example the triangle formed by the coordinate (4,6) would overlap with the coordinate (7,2), thus the correct output would be 2 since only the points (4,6) and (2,5) do not overlap with any created triangles.

So far I have observed that in order to check if a triangle of one point intersects with one of the N points, you take the difference of y-values and check if it is greater than or equal to the absolute value difference of x-values, since the slopes of the triangle sides will always be 1. Using this property my solution uses a quadratic algorithm that compares every point to every other point in the set. However I wish to solve this in linear or linearithmic time, so I need help writing a more efficient algorithm.

Note: the size of the x and y values are very large so I can't use a solution that has iterations based on coordinate sizes.

Upvotes: 0

Views: 245

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59144

Sort the points in descending order of (x+y), using descending order of (y-x) to break ties.

Then, as you iterate through the points in that order, discard points that are overlapped by the triangle of the previous non-discarded point.

The points remaining when you're done are the ones that are not overlapped by any triangle.

Total complexity is O(N log N), dominated by sorting the points.

The proof that this works is based on the fact that the triangle from each point you keep includes all future points that overlap the triangle from the previously-kept point.

Upvotes: 2

Related Questions