今天给各位分享最小圆覆盖算法java的知识，其中也会对最小顶点覆盖的近似算法进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
1、已知n个点坐标，求覆盖所有点的最小面积圆用什么算法?2、最小圆表示什么？3、java能够覆盖凸包的最小圆怎么求
已知n个点坐标，求覆盖所有点的最小面积圆用什么算法?
最简单的算法是任取三个点做一个圆，验证其他n-3个点是否在该圆内，并取遍所有的三个点的组合，记录其中最小的圆。这个算法的复杂度是O(n^4)。
另一种较好的算法是Shamos提出的算法,复杂度是O(nlogn)。
S1. 计算点集S的凸壳CH(S)；
S2. 计算CH(S)的直径，设为p[i]p[j]，以p[i]p[j]为直径做圆C，如果S中的点都在圆C内，则C就是所求的最小覆盖圆；否则转S3；
S3. 计算点集S的最远点意义下的Voronoi图即Vor(S)；
S4. 设v是Vor(S)中的一个Voronoi点，以v为圆心，v至S点集中3个最远点的距离为半径做圆，该圆就是所求。
S1可以在O(nlogn)内完成，S2需要O(n)时间，S3需要O(nlogn)时间，S4的复杂度是O(n)，所以整个算法的复杂度是O(nlogn)。
最小圆表示什么？
最小圆表示的是最小圆覆盖问题的最终结果。最小圆覆盖其实和最小矩形覆盖定义是类似的，给出一个点集，求能覆盖住所有点的最小圆。
最小圆覆盖是数学中的一个算法问题，研究如何寻找能够覆盖平面上一群点的最小圆。这个问题在一般的n维空间中的推广是最小包围球的问题，即寻找能覆盖n维空间中某个点集的最小球。最小圆覆盖问题最早由十九世纪的英国数学家詹姆斯·约瑟夫·西尔维斯特在1857年提出。
最小圆覆盖也是运筹学中设施选址问题的一种。广义的设施选址问题研究的是当已知一些目标点（仓库、销售终端、供应商等等）的位置时，求满足与这些目标点的距离相关的点的某些极值。最小圆覆盖可以看作是研究“到一些点的距离之最大值最小的点”的问题。现有的算法可以在线性时间内计算最小圆覆盖或最小包围球的问题。
寻找最小覆盖圆的大部分几何方法都是寻找给定点集中经过最小覆盖圆的那些点。这是基于以下两个事实：
最小覆盖圆是唯一存在的。
给定的点集中，最多有三个点在最小覆盖圆上。如果有三个点在最小覆盖圆上，那么最小覆盖圆就是这三点的外接圆；如果只有两个点在最小覆盖圆上，那么最小覆盖圆就是以这两点之间的直线段为直径的圆。
扩展资料：
最小覆盖圆的性质：
性质1：最小覆盖圆是唯一的
证明：我们假设有两个圆O1，O2，他们半径都是r，都是最小覆盖圆，那么所有的点一定在两圆的交集部分。那我们以两圆交集部分的弦长为直径，做一个新圆，该圆依旧包含所有点，而且他的直径是原来圆的弦长，一定是小于原来圆的直径的，因此和原来的圆是最小覆盖圆相矛盾，所以最小覆盖圆是唯一的。
性质2：若圆O1是点集S的最小覆盖圆，则再新加一点p，他在集合S的外部，则新点集的最小覆盖圆一定过点p，即p一定在最小覆盖圆上。
同理我们明显能看到，若新的最小覆盖圆将S点集包住也将p包住，过点p的圆半径一定最小。
我们将这个大圆朝原先的小圆缩小，在缩小的过程中一定会过点p，p就是这个临界状态，因为在不断缩小，所以p一定在既包含S又包含p的最小覆盖圆上。
性质3：最终的最小覆盖圆一定只有两种情况：
1是圆上至少有三个点，由三点限制一个圆（三点共圆）；
2是圆上只有两个点，则该圆一定是以该两点的连线为直径的。
如果最小覆盖圆上只有一个点的话，我们肯定可以通过平移加缩小找到一个更小的圆包住所有点，与最小不符。
java能够覆盖凸包的最小圆怎么求
思路：圆覆盖问题只与所有点中凸包上的点有关，因此先求一下凸包，然后数据范围骤减。大概是只剩下logn左右个点。这样就可以随便浪了。
先找所有三个点组成的圆，然后找两个点为直径所组成的圆。
还有就是三角形的外心公式，简直不是人推的。
最小圆覆盖算法java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于最小顶点覆盖的近似算法、最小圆覆盖算法java的信息别忘了在本站进行查找喔。
微信扫一扫 
支付宝扫一扫 
