放置一个点以使到最远点的距离最小 [英] Placing a point to minimise distance from the farthest point

问题描述

我有一个问题，

给出一组点，如何在到最远点的距离尽可能小的约束下放置一个点?

Given a set of points , how do you place a point with the constraint that the distance to the farthest point is as small as possible?.

这是参考此问题.我不知道该如何进行.一些指针有人吗?

This is in reference to this problem. I do not know how to proceed. Some pointers anyone?

谢谢

推荐答案

签出此页面.它描述了执行此操作的几种方法. http://www.personal.kent. edu/〜rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

Check out this page. It describes several methods to do this. http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm

_{万一以上链接消失了，以下是描述最简单方法的相关部分:}

O(n2)时间算法

1. 在中心c处绘制一个圆，以使给定集合的点位于该圆内.显然，可以使这个圆变小(否则我们可以解决).
2. 通过找到距圆环中心最远的点A，并绘制一个具有相同中心的新圆并穿过点A，使圆变小.这两个步骤将产生一个较小的封闭圆.新圆较小的原因是，该新圆仍然包含给定集合的所有点，除了现在它穿过最远的点x而不是将其包围.
3. 如果圆通过2个或更多点，则继续执行步骤4.否则，通过将中心移向点A，直到圆与集合中的另一个点B接触，使圆变小.

4. 在这个阶段，我们通过一个圆C，它穿过给定集合的两个或多个点.如果圆包含的圆弧间隔(无点间隔)大于没有点位于其上的圆周长的一半，则可以使圆变小.令D和E为该无点间隔结束时的点.在将D和E保持在圆的边界上的同时，减小圆的直径，直到出现情况(a)或情况(b).

1. Draw a circle at center, c, such that points of given set lie within the circle. Clearly, this circle can be made smaller (or else we have the solution).
2. Make a circle smaller by finding the point A farthest from the center of circler, and drawing a new circle with the same center and passing through the point A. These two steps produce a smaller enclosing circle. The reason that the new circle is smaller is that this new circle still contains all the points of given set, except now it passes through farthest point, x, rather than enclosing it.
3. If the circle passes through 2 or more points, proceed to step 4. Otherwise, make the circle smaller by moving the center towards point A, until the circle makes contact with another point B from the set.

4. At this stage, we a circle, C, that passes through two or more points of a given set. If the circle contains an interval (point-free interval) of arc greater than half the circle's circumference on which no points lie, the circle can be made smaller. Let D and E be the points at the ends of this point-free interval. While keeping D and E on the circle's boundary, reduce the diameter of the circle until we have either case (a) or case (b).

<情况>(a)直径是距离DE.
• 我们完成了！
• Case (a) The diameter is the distance DE.
  • We are done!
  • 检查是否存在长度大于C圆周一半的无点弧间隔.
  • 如果没有这样的无点电弧间隔退出，则 我们完成了！
  • Check whether there exits point-free arc intervals of length more than half the circumference of C.
  • IF no such point-free arc intervals exit THEN We are done!
  • 转到第4步.
  • 在这种情况下，三个点必须位于长度小于圆周一半的弧线上.我们在圆弧上三个点的外面两个重复第4步.

  此处的另一页上有一个示例小程序: http://www.sunshine2k.de/stuff/Java/Welzl/Welzl.html

  Another page here, with a sample applet: http://www.sunshine2k.de/stuff/Java/Welzl/Welzl.html

  这篇关于放置一个点以使到最远点的距离最小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！