Closest Pair

From Algorithmist
Revision as of 13:21, 5 December 2012 by Topboy1998 (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Line Sweep Algorithm[edit]

See Insert Link Here

Divide and Conquer[edit]

The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows[1]:

  1. Sort points along the x-coordinate
  2. Split the set of points into two equal-sized subsets by a vertical line
  3. Solve the problem recursively in the left and right subsets. This will give the left-side and right-side minimal distances.
  4. Find the minimal distance among the pair of points in which one point lies on the left of the dividing vertical and the second point lies to the right.
  5. The final answer is the minimum among the left, middle, and right deltas.

Originally taken from:

Example Problems[edit]

UVa 10245

Cite error: <ref> tags exist, but no <references/> tag was found