Geometric Algorithms and their Applications

9301259 Agarwal这个项目将探索计算几何的几个领域，包括表面的安排，射线拍摄和隐藏表面去除，近似算法，动态算法和多维搜索。 将特别强调高维问题和涉及非线性对象的问题。 由于并不总是能够获得简单的确定性算法，该项目将为几个困难的问题开发和实现近似和随机算法。 研究的影响将是双重的：（i）发现新的数学技术来解决各种几何问题，以及（ii）开发和实施简单的算法，在实践中工作良好。 ***

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. ***