Annulus Placement Problems: Geometric Algorithms and Applications

本研究的重点是开发和实现几个涉及多边形环区域相对于一组点的最佳放置的问题的有效算法。最优性标准可以是最大化固定大小的环空所包含的点的数量，或者最小化包含固定数量的点所需的环空的大小。环形放置问题的动机是几何公差的应用，移动机器人定位使用测距和模式匹配问题出现在计算机视觉。我们感兴趣的是缩放和偏移环区域，平移和旋转，凸多边形和简单多边形，以及问题的离线和在线变体。

The focus of this research is the development and implementation of efficient algorithms for several problems involving optimal placement of polygonal annulus regions with respect to a set of points. The optimality criteria may be either maximizing the numbers of points contained by a fixed sized annulus, or minimizing the size of the annulus necessary to contain a fixed number of points. The annulus placement problems are motivated by applications in geometric tolerancing, mobile robot localization using range finding, and pattern matching problems arising in computer vision. We are interested in both scaled and offset annulus regions, translation and rotation, convex and simple polygons, and off-line and on-line variants of the problem.