Solving Riddle: Find Closest 2 Points on a Plane in O(N)

  • Thread starter Thread starter Atlas
  • Start date Start date
  • Tags Tags
    Plane Points
AI Thread Summary
The discussion revolves around finding the two closest points on a plane in better than O(N^2) time. Participants mention that while a simple solution exists at O(N * log^2(N)), a more efficient algorithm can achieve O(N * log(N)). A hint suggests considering the problem as minimizing an arbitrary function f(P, Q) of two points, which could lead to a Θ(n²) complexity. A link to a resource on the closest pair problem is provided for further exploration. The conversation highlights the challenge of the riddle and the potential for more efficient algorithms.
Atlas
Messages
5
Reaction score
0
Here's a riddle I'm having trouble solving:
There are N points on a plane. Find the two points that are closest, in time better than O(N^2).

Any idea?
Thanks :)
 
Mathematics news on Phys.org
randomly pick point p. then choose point P+1... :-P
 
Nice problem. Are you sure there is a solution? I'll think on it some more if you know that it can be solved (well, I'll think on it anyways).
 
I know there's a so-called "simple" solution that requires O(N * log^2(N)), and a more complex one that requires O(N * log(N)).
 
Here's a hint:

If the problem was "Given an arbitrary function f(P, Q) of two points, find the pair of points that minimizes f(P, Q)", can you prove that the best algorithm is Θ(n²)?
 

Thread 'Trigonometry problem of interest'

Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
View full post »

Similar threads

I Expressing any given point on plane with one unique number
Replies
4
Views
2K
I The number of intersection graphs of ##n## convex sets in the plane
Replies
2
Views
1K
I Finding vertex of a 3D Triangle on a Plane
Replies
3
Views
2K
B Invariant under rotation: Banal, obvious, or noteworthy?
Replies
2
Views
2K
MHB Vectors in Planes: Solving for m & n, Finding Orthogonal Plane
Replies
2
Views
2K
MHB Planes 1 & 2 Intersect: Find Scalar Equations
Replies
1
Views
1K
B Reprise: Calculate the distance between two points without using a coordinate system
Replies
1
Views
2K
B Existence of parallels in axiomatic plane geometries
Replies
36
Views
5K
I Why fixed point iteration of ##x^3 = 1-x^2## doesn't converge when ##x_0= 0##
Replies
16
Views
587
MHB Nick's Calculus Problem: Find Closest Point on Plane
Replies
1
Views
16K

Hot Threads

Recent Insights

Back
Top