Annulus Placement Problems: Geometric Algorithms and Applications

环面放置问题：几何算法和应用

• 批准号: 9902032
• 负责人: Matthew Dickerson
• 金额: $ 7.5万
• 依托单位: Middlebury College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-08-15 至 2003-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9902032&HistoricalAwards=false
• 关键词: Annulus; Placement; Problems; Geometric; Algorithms

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.

这项研究的重点是开发和实现几个问题的高效算法，涉及到关于一组点的多边形环区域的最优布置。最优性标准可以是最大化固定大小的环形所包含的点数，或者最小化包含固定数目的点所需的环形大小。在几何公差、移动机器人测距定位和计算机视觉中出现的模式匹配问题中，环布局问题的应用受到了广泛的关注。我们对该问题的缩放和偏置环域、平移和旋转、凸多边形和简单多边形以及离线和在线变量都感兴趣。