沃洛诺依（Voronoi）的老虎（转）

最近有限元里面用到了Voronoi的理论，没想到从网上竟然搜到了老虎问题，挺乐的，放到这里。原文如下：

一、两只老虎

       一个老虎，位于一个正方形的野地上。那么这块地的弱小动物将是它的捕获对象。如果这块地上有两个老虎分别蹲在指定的位置上，又假如这两个老虎的捕食能力（如奔跑速度）是同样的，那么怎样划分它俩的捕食范围呢？假定P1及P2处分别为此时此刻老虎的位置。

    如图1所示，只要画出的垂直平分线，则它就划定了老虎的势力范围。

二、三只老虎，三只老虎怎么办？

    大家知道，三角形的三条边的垂直平分线相交于一点。三个老虎的每两个，按图1所示给出了垂直平分线的划分方法，那么三个老虎捕食的势力范围如图2所示。如果老虎此刻排在一条直线上（P1， P2，P3共直线），则划分如图3所示，这是特殊情况。    问题没有完结。如果有四个老虎呢？    这时，我们自然地要看互相离得比较近的老虎，并且相近的两个老虎按其位置点连线的垂直平分线，逐个划分（如图3所示。特殊情况请你作特殊考虑）。
三、N只老虎

    再考虑一般情况，即有N个老虎，此时此刻分别蹲在P1，P2，……PN处，怎样划分其势力范围？图4给出N=16的一种情形。细心地读者可以看出，一个指定的老虎，它的势力范围受它最近的几个老虎的影响，并且都是按这个老虎与邻近老虎的垂直平分线来划定势力范围的。图4(a)中的某个老虎的势力范围是一个多边形，图4(b)则是划分的总图。
四、数学模型

    现在把老虎捕食的问题用数学语言叙述如下：
    （1）给定平面方形区域中N个P1，P2，……PN，对每个Pi，平面中比除了P i之外的点（P1，…，Pi-1，Pi+1，…，PN）更接近于Pi的点（x,y）的轨迹是什么？
    显然，这个问题像是个几何问题，但和已学过的平面几何问题比较，好像完全是不同的“滋味”。的确如此，这样的问题，是属于所谓《计算几何学》问题。这种几何学研究的内容，例如问题（1），所讨论的点和个数N是非常大的数目，目的是当N特别大时，怎样给出问题的答案。也就是说，对人力所不能完成的而必须由计算机帮忙的问题，告诉计算机怎样“机械地、自动地”给出答案。
    上面所述问题（1）中寻求的轨迹，实际上是一类几何图形，就像图1、图2、图3、图4所画的那样，称为沃洛诺依（Voronoi）图。G·沃洛诺依是俄国数学家，他在1908年发表了寻求这类图的论文，后来人们就用他的名字称呼这类图形。也有人称之为Dirichlet区域，Thiessen多边形或Wigner-Seitz单元。还有人用术语“邻近多边形”。

五、应用

    沃洛诺依图有许多重要应用。例如：    在生态学中，如老虎捕食的故事那样，常常需要研究某种生物体的幸存者依赖于邻居的个数，它一定要为食物和光线而竞争；森林中树木种类和动物的沃洛诺依图被用来研究太拥挤产生的后果。    在商业或贸易活动中，用沃洛诺依图来研究竞争中的贸易中心地设置对效益的影响；微观世界中的分子结构是受各种力的综合影响的结果，这里沃洛诺依图是重要的教学工具。    好了，我们看到平面几何中的垂直平分线这样简单的知识，引伸起来产生很复杂、很有用的结果。所以，在简单的问题中，可能蕴藏非常有趣的丰富内容，我们要培养自己，从极简单的问题出发，提出拓广的新问题的能力。哪怕你暂时还不能完全回答你自己提出的新问题，那也不要紧。能自己提出问题，本身就是进步和成功！

    六、问题

    回到沃洛诺依图，见图4，网状的图由点连起来作成。把线段的连接点叫做沃洛诺依图的顶点，点之间的连线叫做边。那么，可提出以下几何问题：
    （1）沃洛诺依图的每一个顶点恰好是图的三条边的公共交点。
    （2）沃洛诺依图的顶点是由原来的点P1，P2，……PN中的三个点确定的圆心。
    可以从图4（b）图中观察到上述结果的正确性。但对一般情形还是需要严格证明的。注意，要作到严格的证明，还不是很简单的，本文不再讨论。