关于某些几何覆盖问题的算法

Algorithms for Some Problems in Geometric Covering

  • 摘要: 提出了求覆盖平面点集最小圆的算法与平面点集中最大空圆的算法.其基本思想是,先把点集S分成若干层,然后逐层求不包围S中点的最大圆并保留之,最后找半径最大的圆.对于包围点集S的最小圆问题,本文提出的算法是,先求点集S的凸包,然后再求包围该凸包顶点的最小圆.

     

    Abstract: Two algorithms are here presented for solving the smallest circle coveing a point-set on a plane and the largest empty circle of a point-set on the plane. The point-set is first divided into a number of layers, then the largest circle not enclosing the points in S is solved for layer by layer and kept The circle of the largest radius is finally found out. For the smallest circle enclosing the point-set S, the algorithm solves for the convex hulls of the point-Set S, then for the smallest circle enclosing the vertex of the convex hulls is found.

     

/

返回文章
返回
Baidu
map