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.