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.