A few examples illustrate the success of computational geometry methods. First, the solution of partial differential equations is fundamental in many areas, e.g., stress analysis, fluid flow, electromagnetic modeling. A mesh is invariably required to solve the partial differential equation numerically. Delaunay triangulations form the basis of essentially all three-dimensional simplicial mesh generators. Computational geometry has provided a solid theoretical and practical understanding of Delaunay triangulations, including asymptotically efficient algorithms, robust implementations, and connections with other geometric structures. Second, prediction of radio propagation is fundamental to the design of wireless communication networks (a topic emphasized in the planned special focus on Next Generation Networks Technologies and Applications). Classical geometric optics and the uniform theory of diffraction provide a sophisticated physical model of radio propagation based on ray-tracing. A naive simulation of the model on a large problem instance might require a day or a week of computing time; computational geometry techniques can provide interactive simulations, allowing a system designer to experiment with variations in network parameters. Third, the prospective technology of `3d photocopying' attempts to characterize an object by sampling points on its surface. Computational geometry has provided algorithms that reconstruct a surface model from the sample points, minimizing the number of required sample points and the deviation from the actual object as well as the required computing time.
This special focus on computational geometry and applications will follow by 13 years the first DIMACS special year on discrete and computational geometry. (Some of the achievements of that special year are described in a report evaluating the accomplishments of the year; see the URL http://dimacs.rutgers.edu/About/Reports/compgeom.html.) During the 13 years, computational geometry has evolved into a mature field with rigorous mathematical foundations. At the same time, there has been a continuing demand for geometric algorithms from affiliated disciplines (graphics, geographic information systems, robotics, VLSI design, computer-aided design and manufacturing, among others). A strong desire has developed within the computational geometry community to improve connections with these and other disciplines. It is timely to have another special focus on computational geometry to exploit these trends, and DIMACS, with its local strength and international connections in the field, is a natural place to have this.
The special focus will deepen the connections between computational geometry and other disciplines. For example, computational geometry and graphics have traditionally been closely tied. However, with changes in technology, e.g., fast cheap PCs and global but relatively slow networks, it may be appropriate to reexamine the algorithmic connections between the two fields. Thus the compression, transmission, and adaptive rendering of meshed models involve combinatorial and topological ideas very much of the flavor of computational geometry; similarly, object-space-based rendering algorithms may become more attractive as the size of models increases. As another example, the solid modeling community has developed in parallel to the computational geometry community. Both communities are concerned with geometric algorithms and have had to deal with many of the same issues, e.g., complexity of representation data structures. The solid modeling community has traditionally been more closely tied to industry and more concerned with curved surfaces; the computational geometry community has been more mathematical and more concerned with linear objects. It is clear that there is considerable potential interaction between the fields, for example on such fundamental conceptual issues as how to describe geometric shapes and how to deal with geometric tolerances. Finally, there are emerging connections with other fields, such as molecular biology (for example through geometric searching).
The special focus will also extend the connections between computational geometry and (mathematical) geometry. The connection with discrete and combinatorial geometry is already well-established, but is sufficiently fundamental to develop further; an intriguing prospective connection is with computational real algebraic geometry. In addition, the special focus will address issues of importance within computational geometry, such as the challenging engineering required to implement geometric algorithms.
Opportunities to Participate: The Special Focus will include:
Index of Special Focus on Computational Geometry and Applications
DIMACS Homepage