CAREER: Pattern Matching, Realistic Input Models and Sensor Placement. UsefulAlgorithms in Computational Geometry

职业：模式匹配、真实输入模型和传感器放置。

• 批准号: 0348000
• 负责人: Alon Efrat
• 金额: $ 40.32万
• 依托单位: University of Arizona
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-03-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0348000&HistoricalAwards=false
• 关键词: CAREER; Pattern; Matching; Realistic; Input

Computational geometry algorithms developed by practitioners in areas such as geographic information science, computer graphics, robotics, and pattern matching tend to be efficient for typical inputs, but inefficient for more complicated inputs. On the other hand, algorithms developed by computational geometry researchers are proved to be valid and efficient even in worst cases, but they are too often difficult to implement or slow in practice. These drawbacks have limited the widespread use of computational geometry techniques in fulfilling the practical needs of application areas. The goal of this research is to bridge the gap between practice and theory by developing algorithms whose correctness and bounds are proven, yet are simple to implement and perform efficiently on real-world inputs.The research focus is two fold. First is geometric pattern matching with biological and medical applications, such as patient positioning in radiation therapy of cancer. Second is an investigation of effective algorithms for realistic input models. The project examines computational geometry algorithms for general classes of inputs that capture realistic data, yet have special properties that enable developing efficient algorithms for them. In particular, the notion of fatness plays an important role in this context. A convex object is called "fat'" if the ratio between its diameter and the radius of the largest ball enclosed in the object is at least some predetermined threshold. For non-convex objects the definition is more involved. In many cases, the worst-case scenario for an algorithm is exhibited only for input objects that are not fat, and these seldom appear in realistic scenarios. The goal of the research here is to develop algorithms, either by tailoring known algorithms or by inventing new ones that are easy to implement and run fast on these classes of inputs. The investigator is developing efficient algorithms for different variants of realistic input models, and also has shown that known algorithms can be executed efficiently for "fat'' objects. The investigator's research (and complementary studies) shows that often these algorithms have guaranteed small asymptotic time bounds, as well as fast running time in practice.

由地理信息科学、计算机图形学、机器人技术和模式匹配等领域的从业者开发的计算几何算法往往对典型输入有效，但对更复杂的输入无效。另一方面，计算几何研究人员开发的算法被证明是有效的，即使在最坏的情况下，但他们往往是难以实现或在实践中缓慢。这些缺点限制了计算几何技术在满足实际应用领域需求方面的广泛应用。本研究的目标是通过开发其正确性和边界已被证明的算法来弥合实践与理论之间的差距，但这些算法易于实现，并且在现实世界的输入上有效地执行。首先是几何图案匹配与生物和医学应用，如癌症放射治疗中的患者定位。第二部分是对现实输入模型的有效算法的研究。该项目研究计算几何算法的一般类的输入，捕捉现实的数据，但有特殊的属性，使他们能够开发有效的算法。特别是，肥胖的概念在这种情况下发挥着重要作用。如果凸形物体的直径与包围在该物体中的最大球的半径之间的比率至少是某个预定阈值，则凸形物体被称为“胖”。对于非凸对象，定义更加复杂。 在许多情况下，算法的最坏情况仅针对不胖的输入对象展示，并且这些很少出现在现实场景中。这里的研究目标是开发算法，无论是通过定制已知的算法，还是通过发明易于实现并在这些输入类别上快速运行的新算法。 研究人员正在为现实输入模型的不同变体开发有效的算法，并且还表明已知算法可以有效地执行“胖”对象。研究人员的研究（和补充研究）表明，这些算法通常保证了小的渐近时间界限，以及在实践中的快速运行时间。