小覆平面上给定点集最盖问题的快速近似新算法及应用

平面上给定点集最小覆盖问题的快速近似新算法及应用

摘要：本文研究了平面中给定点集最小覆盖圆的问题，讨论了求解最小覆盖圆的近似算法，并得到了一种新的算法。文中提出了新的坐标系，并在此新的坐标系中进一步研究快速近似算法，得出新算法的时间复杂度为0（n）。

关键字：最小覆盖；时间复杂度；坐标系；GIS；

1、引言：

求一个最小圆包含给定点集所有点的问题是人们在实践和理论上都十分感兴趣的问题。由于这个圆的圆心是到点集最远点最近的一个点，因而在规划某些设施时很有实用价值。这个圆心也可看成是点集的中心。在图形学中，圆也常可取作边界盒，使用它可减少很多不必要的计算。在空间数据库中可将该问题用于建立空间数据的索引以提高查询速度。这个问题看起来十分简单，但用直观的算法去解此问题，其复杂性可达0（n4），其中n为点集中点的数目［1］。

国际上对于点集的最小覆盖问题有一种统一的算法就是卡马克算法，基于它的思路在平面中已经很好地研究了点集的最小覆盖问题，还解决了平面中给定点集的最小覆盖快速近似算法问题。该问题在雷达布局、导弹布置、卫星通信、交通规划、无线电台广播、日常生活和经济等领域的应用进行了广泛的研究和探讨，并得到了很多成果。