Adjust height of sidebar

KMap# Grant

$427.1K Funding

1 People

External

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.