数学建模社区-数学中国

标题: 距离最近的点对 [打印本页]
作者: 韩冰    时间: 2004-10-4 05:18
标题: 距离最近的点对
<>给定n 个点（xi，yi）（1≤i≤n），要求找出其中距离最近的两个点。
; S. x0 l* q) p0 K) ]$ f: C3 {% u* A; Z1 z  I! g- {
例14-7 假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。' y) L+ P; l* M
. ?, A( z; U( v% c+ w
通过检查所有的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进行递归求解。4 ~- [: l1 o) s4 |. M
# }  l# G) e3 [( a
! x8 T( U3 [: j1 f7 y: |/ D5 s
if (n较小) {用直接法寻找最近点对
. s. X  H9 s) E/ u6 a4 V3 A
* V, Y  n8 {5 lR e t u r n ; }
4 x! {- t1 R- X, O7 u* T  l# w; J1 _, {9 p1 |
// n较大' v  @" [9 \6 [5 P5 ?
5 j: S# t0 O3 n) F7 i9 _
将点集分成大致相等的两个部分A和B. e% P% e7 z' m5 {2 |

  h( {: B1 R! n6 j确定A和B中的最近点对& s3 \3 _5 |8 ?: v# o. l- P

( w# k3 L9 y8 r2 v$ y0 |1 O0 }确定一点在A中、另一点在B中的最近点对! u% F6 Q( {1 R6 D4 f& [- c, z

5 b- s* S' @/ W* `9 H- f; c从上面得到的三对点中，找出距离最小的一对点
1 L7 ~0 O% N1 @. p" F# C( C0 Y9 [* L5 D5 X$ k9 ]5 [: _0 A4 G
图14-13 寻找最近的点对; o9 i# ?* m3 a- D7 C# Q. T

5 d  B" Y" N/ {9 \# ~& e$ C7 R" U" U. y  E' `2 U) Z
为了确定第三种情况下的最近点对，需要采用一种不同的方法。这种方法取决于点集是如何被划分成A、B的。一个合理的划分方法是从xi（中间值）处划一条垂线，线左边的点属于A，线右边的点属于B。位于垂线上的点可在A和B之间分配，以便满足A、B的大小。: I$ V0 E5 B& r, F% ]

: x# V  J; w4 y- T0 A0 C7 k: G: Y  s; i例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。. f, r% C; G, x' G7 D' c, ]

; {+ R" A3 P' v, o设是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）。- o6 w3 |; m% P6 v7 C

8 `5 b7 n2 D) r+ X9 _例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) 是最近的点对。$ O3 E1 t& q) k, O' w

# i8 b8 ~7 w# ^* @9 r/ `& n为了确定一个距离更小的第三类点，RA 中的每个点最多只需和RB 中的6个点比较，如图1 4 - 1 6所示。
; ^& ?  B" g: S8 U% ], R$ _
/ v9 l+ N0 W, y8 W. W: |* e/ {4 z1. 选择数据结构, f2 s# [. m' h! t6 l* b- S; J
% a9 r- c( K2 y: m+ L% s& _- S
为了实现图1 4 - 1 3的分而治之算法，需要确定什么是“小问题”以及如何表示点。由于集合中少于两点时不存在最近点对，因此必须保证分解过程不会产生少于两点的点集。如果将少于四点的点集做为“小问题”，就可以避免产生少于两点的点集。" X$ r3 j5 }5 q+ ~* g; _7 X. v0 ]1 h
4 x4 ]9 v3 a# O; N9 s
每个点可有三个参数：标号， x 坐标，y 坐标。假设标号为整数，每个点可用P o i n t l类（见程序1 4 - 8）来表示。为了便于按x 坐标对各个点排序，可重载操作符＜=。归并排序程序如1 4 -3所示。
$ l) t0 Y( o  A4 @5 F+ S* S2 u  }# W
3 H" V) v1 p5 ?4 Z. g% T程序14-8 点类, _& }* X9 I, K7 S3 L: D8 I* k

- t: g* ^. v0 N, `) L* K& ^3 vclass Point1 {7 a. }& {& P# a  O
  H6 V# W8 _  |% W, X
friend float dist(const Point1&amp;, const Point1&amp;);
8 @: R' s% c3 R
; p4 N! e$ I! c; G7 P0 z. [friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&amp;, Point1&amp;, float&amp;);1 g5 ~1 P1 ?5 x, y$ _8 e

& y+ |$ J) C* [$ p0 Gfriend bool closest(Point1 *, int, Point1&amp;, Point1&amp;,float&amp;);- ^1 d6 I( n8 T5 ]: g4 l# T# ]
% E/ }  ?  x& Z6 T( F/ q. |0 z
friend void main();; ^& k2 V2 l. L3 r: d

1 _1 b' L$ E' }p u b l i c :
7 n- K7 ~5 p  W7 G) I% w+ n2 L$ r" R  G. Q
int operator&lt;=(Point1 a) const
2 H( @: m1 k& a
1 G3 H) ]) T% z1 N' S{return (x &lt;= a.x);}
4 q( Y; E1 D! m$ q  V/ G/ Q
+ _6 B7 _2 y6 v  ip r i v a t e :
9 u- g3 Z0 h* i6 k: v' S$ l8 {3 _& D: x& H
int ID; // 点的编号
' O5 O. Z. J* ~1 m- D1 \' [7 C& a: H, _* g7 y$ K+ G
float x, y; // 点坐标
7 N5 m1 q3 h* U. i; V  \$ I4 o
6 w( O) w2 N# m4 j$ ]1 t} ;
8 s4 Q. U8 B! l4 K: [, T4 G# q1 }# w/ w
class Point2 {
  I+ m7 v( F# w: f6 @6 q, H  R6 N8 h0 [
friend float dist(const Point2&amp;, const Point2&amp;);/ ]8 V( w  b$ p, n& C+ Z  G& ~
/ n5 B% W$ \* n- r1 |7 M! ~
friend void close(Point1 *, Point2 *, Point2 *, int, int, Point1&amp;, Point1&amp;, float&amp;);0 l' B# T& ]3 i" K8 F& l
2 ?- r: I! Z+ i7 e0 j1 k7 u) {
friend bool closest(Point1 *, int, Point1&amp;, Point1&amp;, float&amp;);
: k' Z1 d/ K- y5 q" g& U$ ~' z: @% ^
friend void main();$ L3 ?; d' _% A( G: P- \7 |
8 M. n" l0 y) w6 p; ?) v& T+ M
p u b l i c :
2 t. f7 g$ k7 m  ^3 V8 J; ?' E" V6 v2 B
int operator&lt;=(Point2 a) const3 H+ j- q) t1 S0 g
$ t, H# ?1 [1 M  _4 X
{return (y &lt;= a.y);}) }9 m: M: ]: ^

/ E% @/ y; G( ]" pp r i v a t e :
0 h8 z$ U3 d1 x
/ y& R4 l+ k8 D7 ~$ B0 Z5 ?8 F9 Yint p; // 数组X中相同点的索引
) k. ?1 ?' z) U( Z( f) p; V! B+ L  F* k( ]& V3 G  a
float x, y; // 点坐标3 N! p9 x% P) \; W( B& U1 V% L
$ v4 x6 n4 A$ l. v1 x
} ;& X# r% F: f  |3 @9 {) a
" {2 I6 W0 L5 \% u* ]$ K% L( o0 D7 c
所输入的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中的对应点。
/ z/ `: w, c' U# ~$ L# F+ C3 `) d* T( ~. }4 A1 K
确定了必要的数据结构之后，再来看看所要产生的代码。首先定义一个模板函数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 L! O. e" j! a# O" Q+ C. F, S/ ^' j# K8 @/ a! I- e7 t' K  m( I
程序14-9 计算两点距离
$ _9 @* C, D3 Q2 S2 Q& X9 c- L. R0 I: `3 K" j9 ]* j
template<CLASS T>3 ~. B, w. i- X
) f0 z( k. Q8 ~& X* a1 L8 H% k
inline float dist(const T&amp; u, const T&amp; v)9 |# S7 c" _) j! Q# F( c9 c5 S5 ^: j

' R, N2 ~/ c8 G/ g. w1 _{ / /计算点u 和v之间的距离2 \2 D# p* d/ g9 F: M" ?( Z  @" g$ b
6 n( l+ D  ^$ G
float dx = u.x-v. x ;
; t- b# i. M, m& b: G5 F4 E' g% r: c: M
float dy = u.y-v. y ;0 m- r1 c' F8 R6 L4 M4 n& `
) D0 N) z$ `7 E7 D( s9 W
return sqrt(dx * dx + dy * dy);
- T5 Q% }  `( {8 y; B
7 ^1 d7 H1 X3 U( d( m6 U5 ], ^/ F}
7 `7 e- n- d, w, s; h' d* u) C. ^3 U# \" n' n" B
如果点的数目少于两个，则函数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 )，该函数实际求解最近点对。* P0 s. f% z3 y
, O3 }  \- Q; Y( T- _+ {
程序14-10 预处理及调用c l o s e
+ X% z. _8 E' ~4 ?7 O2 o
6 z4 @) _+ G8 V! C# \bool closest(Point1 X[], int n, Point1&amp; a, Point1&amp; b, float&amp; d)
# a, A0 i0 t: a  L/ R
+ ?0 C3 p3 j  {{// 在n &gt;= 2 个点中寻找最近点对; `, D+ \4 S) C. g- |3 r

# k2 M: Z% |  `0 c+ o4 Q// 如果少于2个点，则返回f a l s e# c4 x0 O  F! X9 |4 t# f# ]  _4 a
6 m* P8 F7 p8 Z+ _2 Y  s
// 否则，在a 和b中返回距离最近的两个点
, O+ q$ G- S  @( F1 _# o- e( P. ?- C# Z- I/ W% Z3 x
if (n &lt; 2) return false;
  o) y- D' G6 z0 L4 `6 I& L* v" m+ S& x8 v
// 按x坐标排序
5 \  f7 t! V8 G9 F) H
3 C+ {3 q$ l$ T7 M0 T1 AM e r g e S o r t ( X , n ) ;
( [. f) K2 q/ ^6 y! l# N  D% T& V/ I* y, Q$ p  S' Y! H/ v2 d
// 创建一个按y坐标排序的点数组2 o! c% q( I" ?# H

8 I3 a3 l6 v. s% }Point2 *Y = new Point2 [n];
4 p6 G# D% G. s7 W, x5 M* H  `4 e8 q0 j/ E
for (int i = 0; i &lt; n; i++) {
4 j: P- W2 W* }5 f) F3 B% W& M
' u. a0 H5 l/ r( N+ @; }// 将点i 从X 复制到Y
8 X, k- ~$ E. `3 R& m' _+ u- A. m9 W+ O
Y.p = i;$ Z) ?% t9 w) ~+ G& C+ h

  c8 O( O* a, ~Y.x = X.x;
9 R& ?+ N0 ]5 S" k9 ]# s  |! s' c* ^
/ ~( K, \' E0 S2 VY.y = X.y;
' Y# O' [% i# B& `- U
0 P  Y6 f7 ], H}
* r% n9 Y  z& m# b
$ ]  y) U  X: y" |: _+ C! ?. ]M e r g e S o r t ( Y,n); // 按y坐标排序3 d! C( J/ ?- _# r) T" O2 K( A
4 b' B$ ]$ S- a% A( e6 M
// 创建临时数组  ~, |8 l) y1 ^

0 ~; ^+ P; L/ K; Y; ~Point2 *Z = new Point2 [n];, |$ j3 Z% Q' t0 y5 G

/ W) n* I* \3 ~: ~' ~+ l, U) k  X// 寻找最近点对
' P" j' v7 x2 B) o  Y( {" d0 M- j; |/ e
. \# m6 H- x0 ~# Q" ~' y5 fc l o s e ( X , Y, Z , 0 , n - 1 , a , b , d ) ;
1 o' p6 z0 ^% L# Z- y; w7 y$ Q. a  C# M7 `+ _
// 删除数组并返回
1 {0 D! c( G( ~$ j/ M  f3 N9 M! E, T/ S, y! B& s& ?
delete [] Y;
& k6 R- I% Q# M; d" q+ w  o
# H0 |! `- x) W8 b- s+ K# sdelete [] Z;
  T- I6 X/ }# t9 o
" m* D1 y* C  _4 _return true;# Y3 Z3 h1 t& ]# u
# F4 X) F1 l3 W1 Y2 ]
}: _- x! `6 ]' O) Q4 v3 D2 `

1 R/ e1 i+ S' R, D- n; _% s8 |& J程序1 4 - 11 计算最近点对6 V& g: |6 L; L0 b% u

6 |! @; ^# c  c% i5 E! {void close(Point1 X[], Point2 Y[], Point2 Z[], int l, int r, Point1&amp; a, Point1&amp; b, float&amp; d)( c) R' L* G1 V

: T8 |5 J4 Q6 w" `{//X[l:r] 按x坐标排序5 s, ^; M( E# B6 d( I7 L
) k# F* w$ ]4 t; Y4 i1 H
//Y[l:r] 按y坐标排序  Y: X; o# ~1 }- a4 M

# t# N3 N& i! T9 T$ fif (r-l == 1) {// 两个点, V: X$ P: F8 n
# h- J2 e. p6 v$ v
a = X[l];1 A" ~0 L: H# L- e
$ I. M1 E/ a! Y# t
b = X[r];1 {$ Y7 i/ t- k" ?7 f* ~& C- h
5 h1 D" R; y/ p
d = dist(X[l], X[r]);
1 N; @8 @: |5 E1 C* i4 _
2 Q, U1 w! A0 i, k' j! f# Er e t u r n ; }+ f+ s) H; i$ ^

/ B3 `7 h2 Y2 u. Lif (r-l == 2) {// 三个点
# K4 V2 N8 D5 N3 ]7 Y+ n9 G
; U( G- M- Y! M8 a; s# |/ T: x- n// 计算所有点对之间的距离
) }6 ]2 G: D8 o) Y
3 ^. I+ W$ n4 N1 i% x% wfloat d1 = dist(X[l], X[l+1]);
9 p" _; w+ P$ B2 ^+ a, L2 R  E+ W+ h9 Y2 Z/ @7 c* |
float d2 = dist(X[l+1], X[r]);
3 d$ ~- _' j! a7 e. U# d
& X& J5 {; K# ^( hfloat d3 = dist(X[l], X[r]);0 v# `2 @8 w% I9 Z: H% k

6 p6 B# b, T: |/ D% F* m: L: t// 寻找最近点对9 i" j- u4 Y3 E- j' @
. s# D( q* T3 y* V) X7 Q- r2 X
if (d1 &lt;= d2 &amp;&amp; d1 &lt;= d3) {& Q* v' r  {% s1 a* ^$ O

& I2 o% i8 o0 oa = X[l];7 c3 a( h9 J' `) G' c/ x
% N+ Z/ J8 }( m; e$ [( n) E7 B
b = X[l+1];
' K; I7 n2 [. Q6 y0 ~  Z& u& P
d = d1;) G$ O) v# l+ f2 m4 o
. Z4 n: [. c/ L) _  A# O' H% Y! h
r e t u r n ; }1 K7 o% E: o+ t/ f' s
; Y3 @2 g/ l" t3 h% n0 }
if (d2 &lt;= d3) {a = X[l+1];8 S* p: f" }; q) W7 G3 n

" W" Q1 {0 z# b! k5 |  h$ Hb = X[r];
- ?! {1 I4 p; y( L! n& y( Z' S0 a8 v" Y4 Y& O5 x
d = d2;}
  s, @2 w& H" ~( D
7 A9 d( D6 C' t& e0 delse {a = X[l];" H, K0 o) l: w3 A

# I* \7 g" C2 L% P3 Sb = X[r];
8 J- E4 p  I! u5 M! N2 A
) D/ A/ u5 |1 b& Pd = d3;}6 H. v( H4 g. V" ~5 @& K: }
5 b+ ~! J: U: c6 ?  D  Q& B; m
r e t u r n ; }
1 D. L' `. q! y( l( G
% t: e4 @; r& H2 K; j/ /多于三个点，划分为两部分
. x, _' u2 {/ L. d& C$ O* s5 V8 r6 T$ U/ Y2 P+ H
int m = (l+r)/2; // X[l:m] 在A中，余下的在B中
( C6 W4 \2 h) r! g) t8 [( E; c) ^8 ~) `& F
// 在Z[l:m] 和Z [ m + 1 : r ]中创建按y排序的表, ]' U6 `# d1 z, T  b
) H0 z0 r) v) N
int f = l, // Z[l:m]的游标: F& C1 E5 q8 H9 u$ N: B1 I% e

9 N' x  X! {9 N7 _9 cg = m+1; // Z[m+1:r]的游标
4 B& `' N$ C# V  H2 z
5 J% s5 J6 J7 m0 _. ^, Xfor (int i = l; i &lt;= r; i++)
7 S1 o1 m7 Q* n  j1 M1 a, X2 o7 R. U5 v3 E& C
if (Y.p &gt; m) Z[g++] = Y;
- W1 {. B; T( D# E, j$ X* z* k; l1 C: u5 z: `% b4 u% p- k
else Z[f++] = Y;
" r2 s5 K6 W4 h: `
. \8 ]" A$ ^( e: Z5 X" U/ p, k# I// 对以上两个部分进行求解$ F( {. G% Z% a4 R3 {

' N8 C. e4 @# l9 y' b- U# ]$ r" ~5 Cc l o s e ( X , Z , Y, l , m , a , b , d ) ;! q  z6 n3 n" X  u; [9 @

! b+ e1 d7 }4 qfloat dr;) i+ a" v$ I/ e9 I) m+ l% H2 P; Z
+ o3 p: P0 c! F- M8 h% b" v
Point1 ar, br;$ m2 Z. G- e$ w9 b4 H

; G6 Y: y5 U& E! Q& y! ^% }c l o s e ( X , Z , Y, m + 1 , r, a r, b r, d r ) ;
7 o/ t; ~$ u) j+ ~/ r+ B; @5 A
# N$ J+ p( j9 b  \, ]9 r4 |// (a,b) 是两者中较近的点对
+ q4 S6 v& L+ r
! k) ~' a; _- }) U  G- r' z/ bif (dr &lt; d) {a = ar;/ {5 [( r; e5 G
# j6 m. ^2 t+ k; [5 B4 V6 l
b = br;
- l+ H4 s. W! [+ v5 U3 E' m  I
, R. d8 ^1 p, V# |$ I" ?3 Od = dr;}) T# a/ ^$ u6 p
8 A  `9 Z; g  p9 i
M e r g e ( Z , Y,l,m,r);// 重构Y
; ~5 t! C* [7 U0 Z
: D7 m) w+ g4 ?* v8 t! \/ /距离小于d的点放入Z" G9 y7 u, A/ u; v

. P9 h; ~: h1 P8 k! V% S3 _8 X3 {int k = l; // Z的游标
- \" g6 Z4 I8 f
) l1 p. U4 d( S3 E, b. ?for (i = l; i &lt;= r; i++)4 }5 `8 O  A8 [- y- ^4 _
. s. u& K: L0 m9 S& q0 m9 c2 c
if (fabs(Y[m].x - Y.x) &lt; d) Z[k++] = Y;
- s/ j) @. c( Y+ `! S) j9 {$ s( \+ G6 F. i: l5 }" s
// 通过检查Z [ l : k - 1 ]中的所有点对，寻找较近的点对
! ^7 p4 F4 T9 j, B6 [9 m, d7 ]+ @# P0 N- q- O5 Q
for (i = l; i &lt; k; i++){' n8 S6 f/ Y7 K' N/ q
7 L4 ^% P, s$ x+ R/ `
for (int j = i+1; j &lt; k &amp;&amp; Z[j].y - Z.y &lt; d;
( e9 {6 X- B- o) h/ @+ i/ Y/ ~" E. L  w9 t
j + + ) {
" g2 K! x" o0 j2 Y6 C2 @3 M* a7 |7 c( k+ ~$ Q0 g- i4 A& D" |# T- u: t/ k
float dp = dist(Z, Z[j]);
3 c7 n, r, N4 _% ~& D4 [: @+ E/ Y- E2 B3 D! V, r7 J
if (dp &lt; d) {// 较近的点对
6 m* B  ^! p, W6 Q; m: a2 B& H' y7 w# m9 t, @) b8 J% R
d = dp;
3 E; c$ Q+ T% @) Z) X9 `. r) J& ~+ ^) ^1 t
a = X[Z.p];( `. _  }3 x0 s) Z/ {7 V4 Z

9 y+ }" d! E* K, ob = X[Z[j].p];}$ i) q  o3 v. c- ]

7 d& }$ g& _0 Y* ~' i3 `}
+ X2 A1 o3 v  k3 O' x5 f/ n& b! E" \) J- f; P9 k& u, }3 A! x
}
8 A! v. ?- g% W* {/ a' `5 L# k, ?  ~- ?8 _8 ]
}
* Y2 m, b# q" h9 n( U5 h- |1 a9 ]5 A( |- u  K
函数c l o s e（见程序1 4 - 11）用来确定X[1:r] 中的最近点对。假定这些点按x 坐标排序。在Y [ 1 : r ]中对这些点按y 坐标排序。Z[ 1 : r ]用来存放中间结果。找到最近点对以后，将在a, b中返回最近点对，在d 中返回距离，数组Y被恢复为输入状态。函数并未修改数组X。6 M7 Z- O3 N8 F% R; I/ I
+ h* m8 U2 |4 N
首先考察“小问题”，即少于四个点的点集。因为分割过程不会产生少于两点的数组，因此只需要处理两点和三点的情形。对于这两种情形，可以尝试所有的可能性。当点数超过三个时，通过计算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 ]。
9 o* _7 C/ ?4 @0 c
; u: f& ~0 t5 n  J% O9 N为实现图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- i1 ^" Y1 z1 T- R. k$ v

/ a( z8 D5 j3 P5 [# d- r$ W# \还是在RB中）与Z[j] 配对来实现，其中i＜j 且Z [ j ] . y - Z [ i ] . y＜ 。对每一个Z [ i ]，在2 × 区域内所检查的点如图1 4 - 1 7所示。由于在每个2 × 子区域内的点至少相距。因此每一个子区域中的点数不会超过四个，所以与Z [ i ]配对的点Z [ j ]最多有七个。
' L* b2 X8 s( J+ f9 R, r7 g' p5 m& ?" W8 O6 d; V# q& @( v1 a; P
2. 复杂性分析
! {% K3 e/ d3 B' G9 o/ B  \4 `# p+ l% J2 p# {" W: L9 h  D
令t (n) 代表处理n 个点时，函数close 所需要的时间。当n＜4时，t (n) 等于某个常数d。当n≥4时，需花费(n) 时间来完成以下工作：将点集划分为两个部分，两次递归调用后重构Y，淘汰距分割线很远的点，寻找更好的第三类点对。两次递归调用需分别耗时t (「n /2ù」和t (?n /2?).
) G3 t5 B8 U7 V: V
1 r) }* C  Z2 j/ E* J# ?, 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