The Algorithm Design Manual Second Edition

Related Problems

: Bandwidth reduction (see page

398

), topological sorting (see

page

481

), scheduling (see page

468

).

---

17

Computational Geometry

Computational geometry is the algorithmic study of geometric problems. Its emer-

gence coincided with application areas such as computer graphics, computer-aided

design/manufacturing, and scientific computing, which together provide much of

the motivation for geometric computing. The past twenty years have seen enor-

mous maturity in computational geometry, resulting in a significant body of useful

algorithms, software, textbooks, and research results.

Good books on computational geometry include:

• de Berg, et al.

[dBvKOS00]

– The “three Mark’s” book is the best general

introduction to the theory of computational geometry and its fundamental

algorithms.

• O’Rourke

[O’R01]

– This is the best practical introduction to compu-

tational geometry. The emphasis is on careful and correct implemen-

tation of geometric algorithms. C and Java code are available from

http://maven.smith.edu/

∼orourke/books/compgeom.html.

• Preparata and Shamos

[PS85]

– Although somewhat out of date, this book

remains a good general introduction to computational geometry, stressing

algorithms for convex hulls, Voronoi diagrams, and intersection detection.

• Goodman and O’Rourke

[GO04]

– This recent collection of survey articles

provides a detailed overview of what is known in most every subfield of dis-

crete and computational geometry.

The leading conference in computational geometry is the ACM Symposium

on Computational Geometry, held annually in late May or early June. Although

the primary results presented at the conference are theoretical, there has been a

S.S. Skiena, The Algorithm Design Manual, 2nd ed., DOI: 10.1007/978-1-84800-070-4 17,

c

 Springer-Verlag London Limited 2008

---

1 7 .

C O M P U T A T I O N A L G E O M E T R Y

563

concerted effort on the part of the research community to increase the presence of

applied, experimental work through video reviews and poster sessions.

There is a growing body of implementations of geometric algorithms. We point

out specific implementations where applicable in the catalog, but the reader should

be particularly aware of CGAL (Computational Geometry Algorithms Library)—

a comprehensive library of geometric algorithms in C++ produced as a result of

a joint European project. Anyone with a serious interest in geometric computing

should check it out at http://www.cgal.org/.

---