Generic Software Foundations for Geometric Computing

Polytechnic University Of New York, Brooklyn NY

Investigators

Abstract

0133599 Bronnimann, Herve Polytechnic Univ of NY Geometric 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.