Year of Award: 1991

Publication Information: The American Mathematical Monthly, vol. 97, 1990, pp. 687-701

Summary: This survey of the field of "computational geometry" includes a discussion on the connection between Voronoi diagrams and convex hulls, an overview of combinatorial geometry, a discussion of space partitions, range search and lower bounds of computational complexity for algorithms.  Specific common techniques are also discussed.

Read the Article: 

About the Author(s): (from The American Mathematical Monthly, vol. 97 (1990)) Ronald Graham, well known to our readers, has won numerous distinctions in mathematics. He is a member of the National Academy of Sciences, has received the Polya prize in combinatorics, is an editor of numerous journals, is a trustee of the AMS, etc. His research is in combinatorics, graph theory, number theory and algorithms.

Frances Yao is now Principal Scientist and Manager of the Theoretical Computer Science Area at Xerox Palo Alto Research Center. She received her Ph.D. in mathematics from MIT in 1973 and has taught at several universities, including Stanford (1976-1979). Her research interests span theoretical computer science, with emphasis on computational geometry.