CODEWITHSUNDEEP
algorithmcomputational-geometry
justAtutor
justAtutor

Reputation: 11

Closest pair of points (linear 1-D case) algorithm

I'm tutoring a student and one of her assignments is to describe an O(nlogn) algorithm for the closest pair of points in the one-dimensional case. But the restriction is she's not allowed to use a divide-and-conquer approach. I understand the two-dimensional case from a question a user posted some years ago. I'll link it in case someone wants to look at it: For 2-D case (plane) - "Closest pair of points" algorithm.

However, for the 1-D case, I can only think of a solution which involves checking each and every point on the line and comparing it to the closest point to the left and right of it. But this solution isn't O(nlogn) since checking each point will take time proportional to n and the comparisons for each point would take time proportional to 2n. I'm not sure where log(n) would come from without using a divide-and-conquer approach.

For some reason, I can't come up with a solution. Any help would be appreciated.

Upvotes: 1

Views: 2087

Answers (2)

Simon
Simon

Reputation: 10841

It seems to me that one could:

  1. Sort the locations into order - O(n log n)
  2. Find the differences between the ordered locations - O(n)
  3. Find the smallest difference - O(n)
  4. The smallest difference defines the two closest points.

The overall result would be O(n log n).

Upvotes: 1

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37980

Hint: If the points were ordered from left to right, what would you do, and what would the complexity be? What is the complexity of ordering the points first?

Upvotes: 2

Related Questions