从给定集合中找出具有最大点密度的最小圆

给定地球表面上一组n个位置的（lat，lon）坐标，找到一个（lat，lon）点c和一个r> 0的值，以便使每个位置的密度d最大化例如，在由c和r定义的圆所描述和包含的表面区域中。

起初我想也许你可以用线性规划解决这个问题。 但是，密度取决于面积取决于r的平方。 二次项。 所以，我认为问题不适用于线性规划。

有没有一种解决这种事情的已知方法？ 假设您将问题简化为笛卡尔平面上的（x，y）坐标。 这是否使它更容易？

你有两个变量c和r，你试图找到最大化密度，这是c和r（和位置，这是一个常数）的函数。 那么也许爬山，梯度下降或模拟退火方法可能会起作用？ 你可以为你的第一个价值做一个很好的猜测。 只需使用位置的质心。 我认为你从那里达到的本地最大值将是全球最大值。

---

脚步：

使用基于密度的聚类算法对您的点进行聚类1;

计算每个群集的密度;

递归地（或迭代地）对最密集簇中的点进行子群集;

该算法必须忽略异常值，并将它们作为自己的群集。 这样，所有高密度的异常值将被保留，并且低密度的异常值将被断开。

跟踪至今观察到的密度最高的聚类。 当您最终到达由单点组成的集群时返回。

---

这个算法只有当你有如下所示的簇时才起作用，因为递归探索会导致类似形状的簇：

---

该算法将会失败，形状不规则，因为您可以看到，即使在计算甜甜圈形状中的密度时，三角形的密度最高，它们会报告密度低得多，而圆心居中[0,0 ]：

---

1.适用于您的一种基于密度的聚类算法是DBSCAN。

链接地址: http://www.djcxy.com/p/84941.html

上一篇: Find smallest circle with maximum density of points from a given set

下一篇: grid point algorithm (finding the point in grid)