CODEWITHSUNDEEP
algorithm
agou
agou

Reputation: 738

Calculate the number of intersections of the given lines

I'm just preparing for Google's phone interview, and run into this question:

Given a list of lines in 2D space, how to calculate the number of intersections in less than O(n^2) time?

They say the interviewee gave out a O(n^2) solution and then the interviewer asked if he could work out a better solution.

Thanks.

Upvotes: 2

Views: 3279

Answers (1)

Ted Hopp
Ted Hopp

Reputation: 234795

Two lines in 2D either intersect once or they are parallel. If no lines are parallel, there are n*(n-1)/2 intersections. An O(n log n) solution is to sort lines by slope, then scan for parallelism, subtracting m*(m-1)/2 for each set of m parallel lines found.

Of course, this ignores any practical issues of floating point roundoff, but I'm assuming that this would have been mentioned in the question if it needed to be considered.

Upvotes: 3

Related Questions