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.