距离最近的点对问题算法

plscareme

最近在看Sedgewick的那本Algorithms in C++，里面在28章有一个关于最近距离的点队的问题求解的算法，分析研究了2天还是有所疑惑，有几个点比较以后，拿出来请教大家，希望能给以一些分析。
主要算法：
算法的主要思想是先比较x坐标，然后比较y坐标，然后用合并排序来选择距离最小的点对：
主要的数据结构，点和链表节点：
struct point
{
    int x;
    int y;
};

struct node
{
    struct point p;
    struct node *next;
};
//全局变量
/* global */
int pass; // 表明比较x还是y坐标
struct node *z; // 尾节电，无限大
float min; // 最短距离
struct point cp1, cp2; // 最短距离点对

//坐标比较函数，pass为一比较x坐标，否则（2）比较y坐标：

int comp(struct node *t)
  { return (pass == 1) ? t->p.x : t->p.y; }
//合并排序函数
struct node *merge(struct node *a, struct node *b)
  {
    struct node *c;
    c = z;
    do
      if (comp(a) < comp(b))
        { c->next = a; c = a; a = a->next; }
      else
        { c->next = b; c = b; b = b->next; }
    while (c != z);
    c = z->next; z->next = z;
    return c;
  }
//距离比较函数

void check(struct point p1, struct point p2)
{
    float dist;
    if ((p1.y != z->p.y) && (p2.y != z->p.y))
    {
        dist = sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));
        if (dist < min)
        {
            min = dist; cp1 = p1; cp2 = p2;
        }
    }
}


// 主要核心比较函数
struct node *sort(struct node *c, int number)
{
    static int sort_i = 0;
    int i;
    struct node *a, *b, *tt;
    float middle;
    struct point p1, p2, p3, p4;
    if (c->next == z)
        return c;
    a = c;
    for (i = 2; i <= number/2; i++)
        c = c->next;
    b = c->next;
    c->next = z;
    if (pass == 2)
    {
        middle = b->p.x;
    }
    //按照Sedgewick的说法,在调用这个merge之前,链表是以x坐标排好序的.
    c = merge(sort(a, number/2), sort(b, number - (number/2)));
    //按照Sedgewick的说法,在这个merge之后, midlle的左右两半的内部点之间的距离,都大于min
    // 这是为什么?
    //为什么这里要比较四个点,为什么四个点足够了,这又是为什么?
    if (pass == 2)
    {
        p1 = z->p; p2 = z->p; p3 = z->p; p4 = z->p;
        for (a = c; a != z; a = a->next)
            if (fabs(a->p.x - middle) < min)
            {
                check(a->p, p1);
                check(a->p, p2);
                check(a->p, p3);
                check(a->p, p4);
                p1 = p2; p2 = p3; p3 = p4; p4 = a->p;
            }
    }
    return c;
}


//主函数

int main()
{
z = new node; z->p.x = max;
              z->p.y = max; z->next = z;
h = new node; h->next = readlist();
min = max;
//第一次pass为1，对x坐标排序
pass = 1; h->next = sort(h->next, N);
//第二次pass为2，对y坐标排序
pass = 2; h->next = sort(h->next, N);
}

plscareme

以前看过一个实现这个问题的算法，也是用的分而治之的算法，但是很复杂，这个算法很简单，可是里面sort函数的实现，确实有些疑惑，不知道怎么实现的左右两个半区的点对的距离都比全局的min大，又怎么实现通过比较四个点就能确保一定找到最近点对的原因？

谢谢！

plscareme

自己顶一下 这个算法有什么问题么

plscareme

继续关注

plscareme

readlist只是一个简单的建立链表的伪函数，没有什么特别的意义，这个算法的实现我是
第一次看到，我以前看到过一个实现，但是非常复杂。
这本书我看的是一本原版书，从别人手上借的，所以也没有电子版。
我是有些迷迷糊糊，关于这个算法，尤其是比较四个点的那个地方，谢谢回复，我也在查找别的
资料，目前还没有什么发现。