Generic Software Foundations for Geometric Computing

几何计算在计算机图形学、机器人技术、建筑学、地理信息系统、空间数据库、实体建模等领域的应用，已经渗透到科学和工程的各个领域，从天体物理学到分子生物学，再到物理模拟和流体动力学。 近年来，人们对二维和大部分三维计算的需求不断增长。 在过去的二十年里，计算几何学家已经研究了这个新生领域的数学基础，并解决了基本几何问题的渐近复杂性。 但是，理论解决方案，虽然带来了宝贵的洞察力的问题，很难回答整个问题，需要一些研究如何设计这些解决方案，使这些见解的好处，以实际解决方案。具体来说，我们建议研究的几何图元和计算几何领域及其许多应用的基础，并开发基本几何对象和谓词的几何概念，以及在各种几何概念的3D一般细分。 将概念的开发与其实现分离的方法论由泛型编程范式支持。 这是一种在算法工程的其他领域取得成功的方法（最著名的是C++标准模板库-STL）。 我们还建议继续我们的investigaion几何算法中的非鲁棒性问题。 解决这个问题的一种方法，这是更有效的比精确计算，是精确的谓词范式，其中只有原语导致关键的决定是保证作出正确的决定，即使数量没有被精确计算。 我们建议研究精确谓词范式的有效实现和影响。 该提案的教育部分加强了研究计划，建议编写一本教科书，专门用于几何计算的实施问题，旨在提供一个基础，并补充现有的经典computaitonal几何教科书。

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.