# Closest Pair

From Algorithmist

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

## 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]}:

- Sort points along the x-coordinate
- Split the set of points into two equal-sized subsets by a vertical line
- Solve the problem recursively in the left and right subsets. This will give the left-side and right-side minimal distances.
- 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.
- The final answer is the minimum among the left, middle, and right deltas.

Originally taken from: http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

## Example Problems[edit]

**Cite error:**

`<ref> tags exist, but no ``<references/> tag was found`

```
```

```
```

```
```