This is a catalog of algorithmic problems that arise commonly in practice. It describes what is known about them and gives suggestions about how best to proceed if the problem arises in your application.

What is the best way to use this catalog?
First, think a little about your problem.
If you recall the name of your problem, look up the catalog
entry in the index or table of contents and start reading.
Read through the *entire* entry, since it contains pointers
to other relevant problems that might be yours.
If you don't find what you are looking for, leaf through the catalog,
looking at the pictures and problem names to see if something strikes a
chord.
Don't be afraid to use the index, for every problem in the book is listed there
under several possible keywords and applications.
If you *still* don't find something relevant, your problem is either not
suitable for attack by combinatorial algorithms
or else you don't fully understand it.
In either case, go back to step one.

The catalog entries contain a variety of different types of information that have never been collected in one place before. Different fields in each entry present information of practical and historical interest.

To make this catalog more easily accessible, we introduce each problem with a pair of graphics representing the problem instance or input on the left and the result of solving the problem on this instance on the right. We have invested considerable thought in selecting stylized images and examples that illustrate desired behaviors, more than just definitions. For example, the minimum spanning tree example illustrates how points can be clustered using minimum spanning trees. We hope that people without a handle on algorithmic terminology can flip through the pictures and identify which problems might be relevant to them. We augment these pictures with more formal written input and problem descriptions in order to eliminate any ambiguity inherent in a purely pictorial representation.

Once you have identified your problem of interest, the discussion section tells you what you should do about it. We describe applications where the problem is likely to arise and special issues associated with data from them. We discuss the kind of results you can hope for or expect and, most importantly, what you should do to get them. For each problem, we outline a quick-and-dirty algorithm and pointers to algorithms to try next if the first attempt is not sufficient. We also identify other, related problems in the catalog.

For most if not all of the problems presented, we identify readily available software implementations, which are discussed in the implementation field of each entry. Many of these routines are quite good, and they can perhaps be plugged directly into your application. Others will be incomplete or inadequate for production use, but they hopefully can provide a good model for your own implementation. In general, the implementations are listed in order of descending usefulness, but we will explicitly recommend the best one available for each problem if a clear winner exists. More detailed information for many of these implementations appears in Chapter . Essentially all of the implementations are available via the WWW site associated with this book, reachable at http://www.cs.sunysb.edu/ algorith.

Finally, in deliberately smaller print, we discuss the history of each problem and present results of primarily theoretical interest. We have attempted to report the best results known for each problem and point out empirical comparisons of algorithms if they exist. This should be of interest to students and researchers, and also to practitioners for whom our recommended solutions prove inadequate and who need to know if anything better is possible.

- Data Structures
- Numerical Problems
- Combinatorial Problems
- Graph Problems: Polynomial-Time
- Graph Problems: Hard Problems
- Computational Geometry
- Robust Geometric Primitives
- Convex Hull
- Triangulation
- Voronoi Diagrams
- Nearest Neighbor Search
- Range Search
- Point Location
- Intersection Detection
- Bin Packing
- Medial-Axis Transformation
- Polygon Partitioning
- Simplifying Polygons
- Shape Similarity
- Motion Planning
- Maintaining Line Arrangements
- Minkowski Sum

- Set and String Problems

Mon Jun 2 23:33:50 EDT 1997