Geometric Algorithms and their Applications

点击翻译按钮获取中文摘要

9301259 Agarwal This project will explore several areas of computational geometry, including arrangements of surfaces, ray shooting and hidden surface removal, approximate algorithms, dynamic algorithms, and multidimensional searching. There will be a special emphasis on higher dimensional problems and on problems involving nonlinear objects. Since it is not always possible to obtain simple deterministic algorithms, the project will develop and implement approximate and randomized algorithms for several hard problems. The impact of the research will be two fold: (i) discovering new mathematical techniques to solve various geometric problems, and (ii) developing and implementing simple algorithms that work well in practice. ***