Generic Software Foundations for Geometric Computing

应用于计算机图形学、机器人、建筑、地理信息系统、空间数据库、实体建模，已经渗透到科学和工程的各个领域，从天体物理到分子生物学，再到物理模拟和流体力学。近年来，人们对二维计算(主要是三维计算)的需求不断增长。在过去的二十年里，计算几何学家研究了这个新兴领域的数学基础，并解决了基本几何问题的渐近复杂性。但是，理论解决方案虽然给问题带来了宝贵的见解，但并不能回答整个问题，需要研究如何设计这些解决方案，将这些见解的好处转化为实际解决方案。具体地说，我们建议研究几何原语和计算几何及其众多应用领域的基础，并为基本几何对象和谓词以及各种几何概念中的3D一般细分开发几何概念。将概念的开发与实现分开的方法论是由泛型编程范例启发的。这是一种在算法工程的其他领域(最著名的是C++标准模板库-STL)获得成功的方法。我们还建议继续研究几何算法中的非稳健性问题。一种比精确计算更有效的解决问题的方法是精确谓词范式，在这种范式中，只有导致关键决策的原语才能保证做出正确的决策，即使数量没有被准确计算出来。我们建议研究精确谓词范式的有效实现和含义。这项提议的教育部分通过提议编写一本致力于几何计算实现问题的教科书来加强研究计划，旨在为现有的经典计算几何教科书提供基础和补充。

0133599Bronnimann, HervePolytechnic Univ of NYGeometric computing, as applied in computer graphics, robotics, architecture, geographic information system, spatial databases, solid modeling, has penetrated every domain of science and engineering, from astrophysics to molecular biology to physical simulations and fluid dynamics. Recent years have witnessed a growing demand for two- and mostly three-dimensional computations. For the past two decades, computational geometers have investigated the mathematical foundations of this nascent field and have solved the asympotic complexity of basic geomteric problems. But theoretical solutions, while bringing valubable insight into the problem, hardly answerthe whole prob lem, and some research is needed on how to engineer these solutions to bring the benefits of these insights into practical solutions. Specifically, we propose to study the geometric primitives and underlying the field of computional geometry and its many applications, and to develop geometric concepts for basic geometric objects and predicates as well as for 3D general subdivisions in various geometric concepts. The methodology of separating the development of concepts from ther implementation is inspried by the generic programming paradigm. This is an approach that has met with success in other fields of algorithm engineering (most notably the C++ Standard Template Library -STL). We also propose to continue our investigaion of non-robustness problems in geometric algorithms. One approach to solving the problem, which is more efficient than exact computation, is the exact predicate paradigm in which only the primitives leading to critical decisions are guaranteed to make the correct decisions, even if quantities are not computed exactly. We propose to study the efficient implementation and implications of the exact predicate paradigm. The educational part of this proposal strengthens the research program by proposing to write a textbook devoted to implementation issues in geometric computing, designed to provide a foundation to and complement the existing classical computaitonal geometry textbooks.