数学建模社区-数学中国

标题: 距离最近的点对 [打印本页]
作者: 韩冰    时间: 2004-10-4 05:18
标题: 距离最近的点对
<>给定n 个点（xi，yi）（1≤i≤n），要求找出其中距离最近的两个点。
. V' y. |* S* v6 ^
7 p" O: ~1 Q2 Y% h例14-7 假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。
+ e& W( T+ a: u; r4 U, q# W9 S, N% ?: c& ~: Z; P
通过检查所有的n(n- 1 ) / 2对点，并计算每一对点的距离，可以找出距离最近的一对点。这种方法所需要的时间为(n2 )。我们称这种方法为直接方法。图1 4 - 1 3中给出了分而治之求解算法的伪代码。该算法对于小的问题采用直接方法求解，而对于大的问题则首先把它划分为两个较小的问题，其中一个问题（称为A）的大小为「n /2ù，另一个问题（称为B）的大小为「n /2ù。初始时，最近的点对可能属于如下三种情形之一： 1) 两点都在A中（即最近的点对落在A中）；2) 两点都在B中；3) 一点在A，一点在B。假定根据这三种情况来确定最近点对，则最近点对是所有三种情况中距离最小的一对点。在第一种情况下可对A进行递归求解，而在第二种情况下可对B进行递归求解。1 c9 e, Y: ~" |4 m* Z7 o
6 j6 v2 T) I$ P# |
* p% q: I- H" I; y
if (n较小) {用直接法寻找最近点对
6 a- V, z3 A% I; \) n. c& R, N. F3 w8 `6 u4 J3 i- O4 {
R e t u r n ; }9 ]3 L1 F; t+ K

$ w  C# I3 j/ M0 J// n较大. e- ]& M' _5 `2 n2 S; m
- K8 B) R, r/ i; b1 p% v8 \7 m4 p" l
将点集分成大致相等的两个部分A和B
+ J* f3 p, J+ o( v
4 f0 R5 {5 K0 y# M/ E" O9 K确定A和B中的最近点对6 U' J# L$ e; d9 R) B( d
4 b6 N# r7 C. L
确定一点在A中、另一点在B中的最近点对( h( C$ z' Z/ T" }! ~/ J& V
, D( T0 c# @* d8 J
从上面得到的三对点中，找出距离最小的一对点
% [% K! G" b6 J! \4 {/ q' A: O( w9 R; j  i7 i9 ]* ~+ I
图14-13 寻找最近的点对
6 N5 Q5 S5 ]- h2 T: W8 O3 B$ b3 R+ O* Z! N

( G* A% J% T4 j0 H& D4 O为了确定第三种情况下的最近点对，需要采用一种不同的方法。这种方法取决于点集是如何被划分成A、B的。一个合理的划分方法是从xi（中间值）处划一条垂线，线左边的点属于A，线右边的点属于B。位于垂线上的点可在A和B之间分配，以便满足A、B的大小。* Q& h$ ]/ e: k5 A8 R& H0 V
  T/ G5 R0 U+ Q* ?# r* O
例2-8 考察图14-14a 中从a到n的1 4个点。这些点标绘在图14-14b 中。中点xi = 1，垂线x = 1如图14-14b 中的虚线所示。虚线左边的点(如b, c, h, n, i)属于A，右边的点(如a, e, f, j, k, l) 属于B。d, g, m 落在垂线上，可将其中两个加入A, 另一个加入B，以便A、B中包含相同的点数。假设d ,m加入A，g加入B。
5 R1 K0 g# W" b, T4 X( u/ Y3 G; r% w3 g* g8 h2 o8 N" `5 g
设是i 的最近点对和B的最近点对中距离较小的一对点。若第三种情况下的最近点对比小。则每一个点距垂线的距离必小于，这样，就可以淘汰那些距垂线距离≥ 的点。图1 4 - 1 5中的虚线是分割线。阴影部分以分割线为中线，宽为2 。边界线及其以外的点均被淘汰掉，只有阴影中的点被保留下来，以便确定是否存在第三类点对（对应于第三种情况）其距离小于。用RA、RB 分别表示A和B中剩下的点。如果存在点对(p,q)，p?A, q?B且p, q 的距离小于，则p?RA，q?RB。可以通过每次检查RA 中一个点来寻找这样的点对。假设考察RA 中的p 点，p的y 坐标为p.y，那么只需检查RB 中满足p.y- ＜q.y＜p.y+ 的q 点，看是否存在与p 间距小于的点。在图14-16a 中给出了包含这种q 点的RB 的范围。因此，只需将RB 中位于×2 阴影内的点逐个与p 配对，以判断p 是否是距离小于的第三类点。这个×2 区域被称为是p 的比较区（comparing region）。
$ s! v4 r! ?' M6 W) k+ g" D. z$ r
例2-9 考察例2 - 8中的1 4个点。A中的最近点对为(b,h)，其距离约为0 . 3 1 6。B中最近点对为(f, j)，其距离为0 . 3，因此= 0 . 3。当考察是否存在第三类点时，除d, g, i, l, m 以外的点均被淘汰，因为它们距分割线x= 1的距离≥ 。RA ={d, i, m}，RB= {g, l}，由于d 和m 的比较区中没有点，只需考察i即可。i 的比较区中仅含点l。计算i 和l的距离，发现它小于，因此(i, l) 是最近的点对。
4 B( E6 \  s* n% \* _
/ q+ @- w/ h) O- k  i: ?为了确定一个距离更小的第三类点，RA 中的每个点最多只需和RB 中的6个点比较，如图1 4 - 1 6所示。4 z* I! h4 @) ~
  T# H* ~) v* s7 V
1. 选择数据结构7 I8 N* g& g& ~4 j: }. E

4 m5 m' e0 f8 W为了实现图1 4 - 1 3的分而治之算法，需要确定什么是“小问题”以及如何表示点。由于集合中少于两点时不存在最近点对，因此必须保证分解过程不会产生少于两点的点集。如果将少于四点的点集做为“小问题”，就可以避免产生少于两点的点集。
0 t  b2 A8 z- A$ E1 q: W
  {4 I5 g7 A* Q: C4 F1 T每个点可有三个参数：标号， x 坐标，y 坐标。假设标号为整数，每个点可用P o i n t l类（见程序1 4 - 8）来表示。为了便于按x 坐标对各个点排序，可重载操作符＜=。归并排序程序如1 4 -3所示。" ?: z# \$ Z. m  n( h; Q' B/ q

. X5 X! J  f- s$ `  X+ j$ a* _程序14-8 点类7 ^' J, K1 y$ z

: @6 m, `4 K/ u; r5 m+ ^( ]class Point1 {
' d1 [8 |4 w) R" P, E! _
7 N) E1 k) @' R; C8 [friend float dist(const Point1&amp;, const Point1&amp;);
' G0 g' N1 G8 a  R4 c( q) F
3 u1 @! ?  B$ U# b; A# i/ [# Q% ]& ofriend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&amp;, Point1&amp;, float&amp;);. Y, P# p! X" I1 S/ j0 T
3 x9 r$ k# |. O
friend bool closest(Point1 *, int, Point1&amp;, Point1&amp;,float&amp;);
5 z; s( @1 c+ W) _3 o! ^# h( Z
, R$ t  p& [7 b" M5 v2 ^. }friend void main();9 k' {! n/ |9 W" @, I6 ]
' F$ `. W  [/ A8 [, z
p u b l i c :! e- a3 {1 F" w- ]6 X5 k! [+ j' J
6 I  r/ |3 P5 {- w% F
int operator&lt;=(Point1 a) const# h6 e# N4 K1 B3 H) i
5 c& z8 N" g8 v; x' \$ Z5 @
{return (x &lt;= a.x);}% F3 \0 {; R- z; y4 Y5 h

6 }7 E! ?" C, p: pp r i v a t e :
' P3 P$ y) J. z6 `+ W* P  j# {' \5 {$ M
int ID; // 点的编号. |" X' o) ?! h8 E( j0 A
! O) c0 G8 @6 w( E
float x, y; // 点坐标
% Q6 J$ p- U/ M( O0 i# k0 \
$ ^& E) Y8 R: T  ^1 ]. p4 I  B} ;- d5 e& @* k1 t6 @
/ f  L0 @* Y* n$ K8 v, O
class Point2 {
2 [; c7 x( E. z' E+ ~: u7 R; D1 s+ I5 `! ^! h" p
friend float dist(const Point2&amp;, const Point2&amp;);
' _" |- X2 \% K3 T: B- `6 t
7 o0 ]. L; V. ?2 E% k0 jfriend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&amp;, Point1&amp;, float&amp;);
! d1 J6 p& R4 f. d0 M! M4 K6 @3 x3 _. g/ X) s7 c. ~
friend bool closest(Point1 *, int, Point1&amp;, Point1&amp;, float&amp;);; b% [$ ?- P: ~
  y; l9 a9 c% e3 |
friend void main();
' c6 h; _7 I6 F* @! P7 A: n/ ?: Z8 L8 ]; D' U2 [4 t3 x" g# T6 [
p u b l i c :
7 |4 x) s4 B6 I1 _
+ h  \) ^, M& g& Q% O( a( Bint operator&lt;=(Point2 a) const9 z) K3 C1 ]* X

6 Z% _3 W1 O0 A{return (y &lt;= a.y);}
" w* Z$ s. y2 Z0 u* O) @1 k& P
3 S% R/ f+ Z! Pp r i v a t e :' a. I6 n; J; G+ n7 S

1 j! o8 o2 s+ X0 b+ s( [! Gint p; // 数组X中相同点的索引/ R2 J: r* Q/ _* }

" [7 k# V. P( j' A9 n* l2 Mfloat x, y; // 点坐标6 G. w% ~; t3 n( B0 _3 F
7 R: T( x! {3 a$ \# K
} ;
. @) a7 E" F- Z, k7 D
$ S7 Q7 Z( a" p' J+ k5 W所输入的n 个点可以用数组X来表示。假设X中的点已按照x 坐标排序，在分割过程中如果当前考察的点是X [l :r]，那么首先计算m= (l+r) / 2，X[ l:m]中的点属于A，剩下的点属于B。计算出A和B中的最近点对之后，还需要计算RA 和RB，然后确定是否存在更近的点对，其中一点属于RA，另一点属于RB。如果点已按y 坐标排序，那么可以用一种很简单的方式来测试图1 4 - 1 6。按y 坐标排序的点保存在另一个使用类P o i n t 2 (见程序14-8) 的数组中。注意到在P o i n t 2类中，为了便于y 坐标排序，已重载了操作符＜＝。成员p 用于指向X中的对应点。3 L" q6 o0 V2 r0 d

, G+ `+ r1 B8 Y, D确定了必要的数据结构之后，再来看看所要产生的代码。首先定义一个模板函数d i s t (见程序1 4 - 9 )来计算点a, b 之间的距离。T可能是P o i n t 1或P o i n t 2，因此d i s t必须是P o i n t 1和P o i n t 2类的友元。3 n, S8 M2 \* r  h/ y

& h$ i, l# K0 ~8 P7 ^9 {程序14-9 计算两点距离
! K  d7 Q* |1 c) H7 }! }5 u# p0 J; d+ b2 B
template<CLASS T>
* W8 w, {# Q! R* D7 a7 b9 t7 p4 g: J! R- V  H
inline float dist(const T&amp; u, const T&amp; v)
- U8 Z+ t; Z5 u( x/ @0 G; t) g& @. a) J
{ / /计算点u 和v之间的距离
! B, _- R9 b9 U. L+ W  I" O
' n) F# f- F2 s5 L: Z0 T5 ~float dx = u.x-v. x ;
1 B1 Z7 s3 c6 w, W0 [* ^
5 a' P1 J' K& O, a% c2 lfloat dy = u.y-v. y ;( |. |4 C' T4 N
2 B7 m9 K$ q7 \% R9 A# }* a) U& r
return sqrt(dx * dx + dy * dy);
* ~/ P5 n  X( p/ F/ a  E( v' D
. J' P3 L  o- |. D9 M}5 S, J  J; K2 a7 G6 p( m: M5 y

7 [. a$ z& m" p/ S7 _" S如果点的数目少于两个，则函数c l o s e s t (见程序1 4 - 1 0 )返回f a l s e，如果成功时函数返回t r u e。当函数成功时，在参数a 和b 中返回距离最近的两个点，在参数d 中返回距离。代码首先验证至少存在两点，然后使用M e rg e S o r t函数(见程序14-3) 按x 坐标对X中的点排序。接下来把这些点复制到数组Y中并按y 坐标进行排序。排序完成时，对任一个i，有Y [i ] . y≤Y [i+ 1 ] . y，并且Y [i ] .p给出了点i 在X中的位置。上述准备工作做完以后，调用函数close (见程序1 4 - 11 )，该函数实际求解最近点对。% d3 V- |7 N% \  x

6 U9 k& `$ I' g3 m5 t( B% z0 j程序14-10 预处理及调用c l o s e- \) K# x# ]  }6 S2 b3 ?* E7 ^

8 d% E+ w8 x  L. {* ?1 @bool closest(Point1 X[], int n, Point1&amp; a, Point1&amp; b, float&amp; d)
+ l" e+ [& l% R4 m# B3 F; R# a! O/ @7 w7 B
{// 在n &gt;= 2 个点中寻找最近点对! w/ ~+ E. g" A, C( ?" ~

9 W/ L* ^0 B/ R& Y; M// 如果少于2个点，则返回f a l s e
* u1 E+ s" K2 }, G! a) D. ~$ y9 W5 y% Q% d/ b; F
// 否则，在a 和b中返回距离最近的两个点
( z* M( j! _7 J/ f/ o* m! c1 i- Y3 |, W' b9 E
if (n &lt; 2) return false;7 {' ]) e6 _6 u  C4 H, h, \
, m( p. V! A! h: R
// 按x坐标排序0 t& r" [5 g* z! T& u0 G2 O
: z2 w6 q; U1 s4 P# }$ z- J% p# E
M e r g e S o r t ( X , n ) ;# t* U/ T+ g, [7 V: N6 q

, t0 U$ P0 @1 I7 P& E5 @1 ~// 创建一个按y坐标排序的点数组) b, u  Q' v* P" M7 _4 m8 ^0 D6 D. Y
7 K4 Q) l0 I' ^7 }
Point2 *Y = new Point2 [n];& Z6 U1 }2 b' h) r8 H

+ G+ u/ U+ M/ G! {+ z# Z& Nfor (int i = 0; i &lt; n; i++) {
9 C9 K& ?4 Y; s8 J/ \
0 t" E* d1 W1 Z5 t' X' q, F// 将点i 从X 复制到Y
. F% t" L5 j1 R- r* J
% b% h4 b0 y  f6 y# g% n6 q9 d* M' IY.p = i;
6 g5 m$ G( X: h+ e
1 u; ~8 Q6 a3 |* I0 eY.x = X.x;
5 e9 _# m* I( q; c3 @7 X
7 x. @; T7 D3 Y8 q4 H" ^, s* kY.y = X.y;' T! ?# I  p5 ~) O  J. C' M# x" m* n

" c7 i! d2 h2 F" y+ q- B}) a% ~2 H0 ~1 ~) s2 `. e/ B/ t

1 v1 L7 T/ W) w. L  O& KM e r g e S o r t ( Y,n); // 按y坐标排序7 H! W; f- G* o; J& O
, S7 Z) c- O1 L
// 创建临时数组4 A0 S& E4 c, k% N% `  T4 I

2 H3 n. I8 O+ g+ jPoint2 *Z = new Point2 [n];) q" o& H: |4 F8 M7 A! ?

" p& O5 H4 s, a& j// 寻找最近点对/ g, g0 _, ~. F

+ k5 A( C6 v9 f+ P& W- [c l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;$ c- K0 |9 p3 ]
6 U- u- Q+ g3 F$ p9 j. q
// 删除数组并返回
$ E5 ]) _6 E6 D* J2 P2 l2 u9 \- [) M: N; T5 |
delete [] Y;
7 u4 }1 e% H4 m* X0 o
, L+ J+ B( h. d! \$ m( sdelete [] Z;9 X- B1 e2 U6 I  d. s

' d0 I( y  c7 b2 [5 N" zreturn true;
: C. j6 D- _2 D5 @- W
! s0 |" D6 F5 r8 y}) K: F$ T% V& [& V0 M* U
' f" w3 J4 s3 S" B3 {
程序1 4 - 11 计算最近点对
7 x. T9 _' u4 t( l0 w5 C7 O& [# e0 r- l. |
void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1&amp; a, Point1&amp; b, float&amp; d)
% l( b/ Q5 B1 q% A9 v0 `0 p. _$ s/ p. p& l1 z
{//X[l:r] 按x坐标排序
% a4 d: J9 w* w( e! ?2 v/ j$ o; r  t2 H; S0 d1 ~
//Y[l:r] 按y坐标排序( s1 |* @3 `1 D

  m4 y+ X3 z5 f! U0 M: Q8 U1 f) y7 }* aif (r-l == 1) {// 两个点7 o, k# A) f% F: {/ U
$ I9 O1 ], ]  x
a = X[l];
" K8 o$ h6 o; i$ J6 [: H, H
1 M& Z& Z! Q7 f% [: ?+ hb = X[r];8 q7 S6 B5 d8 @1 r

: `: Z3 I- j9 z) V' pd = dist(X[l], X[r]);! B' J. s% ?3 d# D
& x5 W* k% t# s: {/ ~
r e t u r n ; }2 U2 t- \1 x' L# o8 X; p
! [7 Q1 {1 A* z* W6 \( L
if (r-l == 2) {// 三个点: g; m/ [# p% g+ ?6 o. `4 x! z

9 n, b# h# j) B3 c) R// 计算所有点对之间的距离8 x' s" G3 o1 o" L# x3 ~

  O4 m2 I5 s: E3 ofloat d1 = dist(X[l], X[l+1]);. Y2 Y# S9 I3 }5 Q2 |" T/ ]$ S! U
, P0 x) u) g3 o9 t
float d2 = dist(X[l+1], X[r]);- g3 ]1 R7 L  X( ]

. [) J+ f% s$ P* X) ?( Hfloat d3 = dist(X[l], X[r]);
" E! D) d: f! `% M& s: _/ {3 {
& s1 a, K4 f, m* S! U, n- [1 {" {// 寻找最近点对/ j$ v& W# v: {  x% v+ X. Z% G/ a

0 T( v* w2 ~+ N  A8 y' O" p1 Bif (d1 &lt;= d2 &amp;&amp; d1 &lt;= d3) {
" @& O0 a1 k# @4 T4 p4 U: r$ L7 r& S* z/ ~" x
a = X[l];
. D# G/ P0 s9 S/ M
7 N( z* H1 b* ^7 q# J* X+ L, }b = X[l+1];- z7 P& g/ g& T5 Q" y* o5 J. {
# O2 T' A: [- Q+ t
d = d1;
- L# M# O' g. g+ _0 H
, @" A8 Z& q& D* @, Xr e t u r n ; }  V" N+ k7 v/ S

: U' ?( X# `6 C5 _if (d2 &lt;= d3) {a = X[l+1];' p( g9 G8 \' H) @0 ]5 w/ \) q

, \- D6 Y6 A3 r7 n! d& gb = X[r];
' i# i$ K% ~8 C5 ]3 K3 [1 X* E6 j6 a% r' D
d = d2;}. i+ ]% [; z; v5 ~1 q% \; P2 a; x
$ Z% Y1 c6 }" K/ ]! e5 ~5 `; F/ [8 t
else {a = X[l];* r7 M# O6 |( K0 n
" R$ g+ B# w+ n0 c3 ~
b = X[r];
* {/ z: n" u; x# t+ s  ~7 G& r- [" b& m  ^# t
d = d3;}- \' P  X* E7 @: p/ p/ F/ ~* f
$ I+ [3 G' |* _4 }* x( F5 f' G% j7 u
r e t u r n ; }
! U* t) [* c: g+ N, r
1 ?! i, Q  |0 a$ v/ /多于三个点，划分为两部分
" W- ]1 P2 }2 v4 y+ O
% b7 S8 |8 a$ V2 qint m = (l+r)/2; // X[l:m] 在A中，余下的在B中! w' i; ~' W' o% v  W9 s7 f
4 k; x8 M  @& o* C! s* h
// 在Z[l:m] 和Z [ m + 1 : r ]中创建按y排序的表  d% I& X4 N# E7 z6 Y
+ b5 Z  ]& a4 C; L3 J$ I! J
int f = l, // Z[l:m]的游标
3 W( `+ [/ A' Z' r5 o( ?; l3 y" k1 k, U
g = m+1; // Z[m+1:r]的游标
$ n7 E' x. t$ t3 W) ?3 t
/ C: I6 E) n5 P. p. gfor (int i = l; i &lt;= r; i++)- X, n- R6 Z4 A/ z1 m" x9 d3 P

+ X6 n" j" \: {# mif (Y.p &gt; m) Z[g++] = Y;% X9 B! ~4 Q7 K

9 N9 w" C/ a8 f' b* eelse Z[f++] = Y;; j7 g. w9 h7 |8 b
8 ]" s$ f- f& g
// 对以上两个部分进行求解
- \- T0 E: T9 z+ h* ~
9 ^! Y0 p) ^9 @1 Oc l o s e ( X , Z , Y, l , m , a , b , d ) ;
9 b1 v0 Y! F( I5 _% R& Y7 m4 Z$ H& v9 z2 C/ n# b$ u* [& t& W" Z; N
float dr;1 [4 L  l9 r1 Y5 G
6 a9 e8 S" m% N+ j) u" V
Point1 ar, br;
5 j/ _  \  ~- h) l0 E' g, M  F: w/ N5 T, g+ {. e' o
c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ;
6 j7 o  M1 b& @- ~( j; P7 W" A* v5 c8 ]9 `) S8 S% Q/ U1 @
// (a,b) 是两者中较近的点对: O/ y, L2 c; `2 [) m) s
) h( _: p* \4 z- D$ z% A% k
if (dr &lt; d) {a = ar;, l3 l) h/ q# d) R) j- O% n

7 f2 O, Q; R4 F+ [0 cb = br;
* c( Y: R+ u! S% Y% G# ^* n1 j# B1 N7 R* O1 L) s* N
d = dr;}+ `' k/ F* N1 A2 P5 j5 ~. ]' z

" m6 n# S8 c0 d2 nM e r g e ( Z , Y,l,m,r);// 重构Y
$ N) I) s% O' T! J9 V7 ]% m7 l4 u  _
4 D; T( K( O7 M" C! [7 O" l& b( `/ /距离小于d的点放入Z
5 V7 ?4 R( J, p. }" @3 ^/ S8 H7 w+ h  f' h. M) {
int k = l; // Z的游标
$ n; B0 R; e5 J9 U; A2 b
. \6 s9 \8 k! p; Sfor (i = l; i &lt;= r; i++)1 Y$ Z) J, {1 i5 P4 n+ ~

* M2 o. d. X) R* w/ eif (fabs(Y[m].x - Y.x) &lt; d) Z[k++] = Y;3 q; v2 J  y5 z9 D5 e7 i

0 M4 u: ]) [# j* |0 l/ b$ \) n// 通过检查Z [ l : k - 1 ]中的所有点对，寻找较近的点对
, @  r* m0 N/ |5 Z
; `# w4 O3 w4 o5 _  @: U/ ]) @for (i = l; i &lt; k; i++){; _2 j1 s, u0 R" S1 |5 u  @  ~2 G

1 ~2 K9 @) ]. z1 f) Z/ |" [+ Ffor (int j = i+1; j &lt; k &amp;&amp; Z[j].y - Z.y &lt; d;
: ^8 V  v& L8 M4 `/ F3 F0 W4 d5 y# W* y8 b: Y/ t7 k# C4 q5 D
j + + ) {) W6 n8 y9 `0 [1 r
; ]6 b) B: i! }& o0 b6 W- v6 R% E! ?
float dp = dist(Z, Z[j]);  J3 g6 _* [2 `- D& C- i

/ a$ l& S# H# k8 k, _if (dp &lt; d) {// 较近的点对
) q3 l! [( m& `4 H7 m+ V4 x( j2 O0 {/ I# S# R
d = dp;- n/ ], T$ n0 @' T* q

. c% g- e( G% T4 ia = X[Z.p];  C! o. {3 B+ ?

* _8 [1 i7 w0 }4 T: d- [b = X[Z[j].p];}
4 y* H" R& q% b. j4 I( G
2 N5 A* }2 p$ F! e  p}
5 y6 ?8 x/ M; e. R8 T9 T2 b4 ~
4 q( V: `1 Z  V' Q}( \* i# s: J4 K' O; E+ R
& `% n+ P1 C. a
}# F7 }, P1 L9 a0 l4 |8 _

- ?7 ~+ l3 e' D函数c l o s e（见程序1 4 - 11）用来确定X[1:r] 中的最近点对。假定这些点按x 坐标排序。在Y [ 1 : r ]中对这些点按y 坐标排序。Z[ 1 : r ]用来存放中间结果。找到最近点对以后，将在a, b中返回最近点对，在d 中返回距离，数组Y被恢复为输入状态。函数并未修改数组X。
) N9 A' g/ o+ J/ E' ]
" |5 O! x0 u! @1 T8 u6 c# r首先考察“小问题”，即少于四个点的点集。因为分割过程不会产生少于两点的数组，因此只需要处理两点和三点的情形。对于这两种情形，可以尝试所有的可能性。当点数超过三个时，通过计算m = ( 1 + r ) / 2把点集分为两组A和B，X [ 1 : m ]属于A，X [ m + 1 : r ]属于B。通过从左至右扫描Y中的点以及确定哪些点属于A，哪些点属于B，可以创建分别与A组和B组对应的，按y 坐标排序的Z [ 1 : m ]和Z [ m + 1 : r ]。此时Y和Z的角色互相交换，依次执行两个递归调用来获取A和B中的最近点对。在两次递归调用返回后，必须保证Z不发生改变，但对Y则无此要求。不过，仅Y [ l : r ]可能会发生改变。通过合并操作（见程序1 4 - 5）可以以Z [ 1 : r ]重构Y [ 1 : r ]。( m/ l+ y+ _' l, ?, N8 y7 B

) |* b4 u. k% t- y: l  \7 O! ?为实现图1 4 - 1 6的策略，首先扫描Y [ 1 : r ]，并收集距分割线小于的点，将这些点存放在Z [ 1 : k - 1 ]中。可按如下两种方式来把RA中点p 与p 的比较区内的所有点进行配对：1) 与RB 中y 坐标≥p.y 的点配对；2) 与y 坐标≤p.y 的点配对。这可以通过将每个点Z [ i ]（1≤i &lt; k，不管该点是在RA
2 v0 Y& ^" g4 X, [" A
, }9 H* w* B# K. _还是在RB中）与Z[j] 配对来实现，其中i＜j 且Z [ j ] . y - Z [ i ] . y＜ 。对每一个Z [ i ]，在2 × 区域内所检查的点如图1 4 - 1 7所示。由于在每个2 × 子区域内的点至少相距。因此每一个子区域中的点数不会超过四个，所以与Z [ i ]配对的点Z [ j ]最多有七个。1 Z& C: K  D9 p" _0 N

9 R6 j* b* a% H: W' @1 p2. 复杂性分析7 }  B2 j9 S/ k6 C; Q; Q
# T7 C! A& k1 e* k9 b+ g3 X* }
令t (n) 代表处理n 个点时，函数close 所需要的时间。当n＜4时，t (n) 等于某个常数d。当n≥4时，需花费(n) 时间来完成以下工作：将点集划分为两个部分，两次递归调用后重构Y，淘汰距分割线很远的点，寻找更好的第三类点对。两次递归调用需分别耗时t (「n /2ù」和t (?n /2?).# |# n4 i7 l3 [* ]' ^% u' _5 B4 \

! f% o# s- T! J' L/ F0 ?! F这个递归式与归并排序的递归式完全一样，其结果为t (n) = (nl o gn)。另外，函数c l o s e s t还需耗时(nl o gn)来完成如下额外工作：对X进行排序，创建Y和Z，对Y进行排序。因此分而治之最近点对求解算法的时间复杂性为(nl o gn)。</P>



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5