Algorithms

The algorithmic angle as a scientific methodology in its own right has developed with the rise of computer science as an independent discipline. It would be interesting to apply algorithmic thinking directly to large-scale and parallel computations, as they happen within every living organism. The recommended literature is grouped into six categories.

Combinatorial Algorithms.   The focus in this category is on the logical structure of processes. How can we arrange the flow of computations to avoid redundancy and do the job as efficiently as possible? A comprehensive introduction to this field is the book by Cormen, Leiserson, and Rivest [1]. Important subareas are graph algorithms and combinatorial optimization, for which we recommend the book by Lawler [2].

Numerical Algorithms.   Algorithms for numerical problems, such as the solution of a system of linear equations, are historically older than combinatorial algorithms. Important subareas are linear algebra [3] and matrix algorithms [4]. Many of the numerical algorithms that have applications in scientific computing are collected and conveniently packaged in the numerical recipes book [5].

Computational Geometry.   Problems in geometry require a mixture of combinatorial and numerical methods. The proportions vary, but by and large the research in this area focuses on the combinatorial aspects and aims of designing algorithms that are efficient. We recommend the introductory text by de Berg, van Kreveld, Overmars and Schwarzkopf [6] and the book by Edelsbrunner [7], which focuses on Delaunay triangulation and mesh generation.

Geometric Design.   This field grew out of an effort to computerize the design work in the automobile and other industries. One branch of the field is concerned with the design of smooth surfaces that bound mechanical shapes, and we recommend the text by Farin [8]. Another branch represents shapes as solids and thus approaches design from a rather different angle [9]. The generation of meshes that decompose such solids into single pieces connects this work with computational geometry and with numerical algorithms.

Computer Graphics.   The traditional focus of computer graphics is the generation of images and pictures. A popular text in the area is the book by Foley, van Dam, Feiner and Hughes [10]. A subarea is virtual reality, which studies three-dimensional interfaces between humans and the computer. In this subarea, the fidelity of representations of geometry is important and the boundaries to geometric design and computational geometry are blurred.

Robotics.   Two subareas of robotics are computer vision and motion planning. Both study algorithms for geometric problems that arise in the construction of a robot and in programming its interaction with the environment. We recommend the book by Latombe [11] on the subject.


References:
[1] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge MA, 1990.
[2] E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Saunders College Publishing, Fort Worth TX, 1976.
[3] G. Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press, Wellesley MA, 1993.
[4] G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore MD, 1996.
[5] B. P. Flannery, W. H. Press, S. A. Teukolsky, W. T. Vetterling. Numerical Recipes in C. Cambridge University Press, Cambridge, England, 1992.
[6] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry. Springer-Verlag, New York, 2000.
[7] H. Edelsbrunner. Geometry and Topology for Mesh Generation. Cambridge University Press, England, 2001.
[8] G. Farin. Curves and Surfaces for Computer Aided Geometric Design. Academic Press, San Diego CA, 1997.
[9] M. Mantyla. An Introduction to Solid Modeling. Computer Sciences Press, Rockville MD, 1988.
[10] J. D. Foley, A. van Dam, S. K. Feiner, J. F. Hughes. Computer Graphics. Addison-Wesley, Reading MA, 1990.
[11] J.-C. Latombe. Robot Motion Planning. Kluwer, Boston, 1991.