最近点对问题（Closest Pair of Points）
📌 定义
给定平面上的n个点，找出距离最近的两个点。这是计算几何中的经典问题，暴力解法需要O(n²)时间，而使用分治算法可以优化到O(n log n)。
示例:
点集: [(1,1), (3,3), (2,2), (5,5), (4,4)]
最近点对: (2,2) 和 (3,3)
距离: √[(3-2)² + (3-2)²] = √2 ≈ 1.414
核心思路
使用分治法：
- 分解：将点集按x坐标排序，从中间分成左右两部分
- 递归：分别找出左半部分和右半部分的最近点对
- 合并：检查跨越分割线的点对，更新最小距离
关键优化：合并时只需检查距离分割线距离小于δ的点，且这些点按y坐标排序后只需检查相邻的几个点。
点集按x坐标分割:
|
● | ●
● | ●
● | ●
| ●
● | ●
|
左半 右半
最近点对可能在:
1. 完全在左半部分
2. 完全在右半部分
3. 跨越分割线
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(n²) | O(1) | 检查所有点对 |
| 分治法 | O(n log n) | O(n) | 预排序+分治 |
Go 代码
Go 实现
package main
import (
"fmt"
"math"
"sort"
)
type Point struct {
X, Y float64
}
func distance(p1, p2 Point) float64 {
dx := p1.X - p2.X
dy := p1.Y - p2.Y
return math.Sqrt(dx*dx + dy*dy)
}
func closestPair(points []Point) (float64, Point, Point) {
// 预处理：排序
px := make([]Point, len(points))
py := make([]Point, len(points))
copy(px, points)
copy(py, points)
sort.Slice(px, func(i, j int) bool {
return px[i].X < px[j].X
})
sort.Slice(py, func(i, j int) bool {
return py[i].Y < py[j].Y
})
return closestPairRec(px, py)
}
func closestPairRec(px, py []Point) (float64, Point, Point) {
n := len(px)
// 基准情况
if n <= 3 {
return bruteForce(px)
}
mid := n / 2
midPoint := px[mid]
// 分割
var pyl, pyr []Point
for _, p := range py {
if p.X <= midPoint.X {
pyl = append(pyl, p)
} else {
pyr = append(pyr, p)
}
}
// 递归
dl, p1l, p2l := closestPairRec(px[:mid], pyl)
dr, p1r, p2r := closestPairRec(px[mid:], pyr)
var d float64
var p1, p2 Point
if dl < dr {
d = dl
p1, p2 = p1l, p2l
} else {
d = dr
p1, p2 = p1r, p2r
}
// 检查strip
var strip []Point
for _, p := range py {
if math.Abs(p.X-midPoint.X) < d {
strip = append(strip, p)
}
}
for i := 0; i < len(strip); i++ {
j := i + 1
for j < len(strip) && (strip[j].Y-strip[i].Y) < d {
dist := distance(strip[i], strip[j])
if dist < d {
d = dist
p1, p2 = strip[i], strip[j]
}
j++
}
}
return d, p1, p2
}
func bruteForce(points []Point) (float64, Point, Point) {
minDist := math.Inf(1)
var p1, p2 Point
for i := 0; i < len(points); i++ {
for j := i + 1; j < len(points); j++ {
d := distance(points[i], points[j])
if d < minDist {
minDist = d
p1, p2 = points[i], points[j]
}
}
}
return minDist, p1, p2
}
func main() {
points := []Point{
{1, 1}, {3, 3}, {2, 2}, {5, 5}, {4, 4}, {7, 1}, {8, 9},
}
minDist, p1, p2 := closestPair(points)
fmt.Printf("最近点对: (%.1f,%.1f) 和 (%.1f,%.1f)\n", p1.X, p1.Y, p2.X, p2.Y)
fmt.Printf("最小距离: %.4f\n", minDist)
}思路展开
为什么只需检查7个点？
关键观察:
在strip中，对于任意点p，在距离d内的矩形区域中：
- 矩形大小: 2d × d
- 左半部分 d × d 最多4个点（否则距离<d）
- 右半部分 d × d 最多4个点
- 总共最多8个点（包括p自己）
因此只需检查后面最多7个点！
复杂度推导
T(n) = 求解n个点的最近点对时间
T(n) = 2T(n/2) + O(n)
↑ ↑
递归求解 合并
其中合并步骤:
- 构建strip: O(n)
- 检查strip: O(n) (每个点最多检查7个)
根据主定理:
a = 2, b = 2, f(n) = O(n)
log_b(a) = log_2(2) = 1
因为 f(n) = Θ(n^1)
所以 T(n) = O(n log n)
经典题目
基础应用
- 最近点对距离
- 所有最近点对
- K最近点对
扩展问题
- 三维空间最近点对
- 曼哈顿距离最近点对
- 动态最近点对（支持插入删除）
⚖️ 优缺点
优点
- ✅ 高效：O(n log n)
- ✅ 最优：已被证明是最优算法
- ✅ 可扩展：可推广到高维空间
缺点
- ❌ 实现复杂：需要仔细处理边界情况
- ❌ 空间开销：需要额外的排序数组
🎨 应用场景
- 计算几何：最近邻查询
- 聚类分析：数据点分组
- 碰撞检测：游戏和物理模拟
- 地理信息系统：找最近的设施
- 模式识别：特征匹配