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

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

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.