Computational geometry is the branch of computer science concerned with the design and analysis of algorithms for geometric problems. Among the tools of computational geometry there seems to be a small set of techniques and structures that have such a wide range of applications that they deserve to be called fundamental, in the same sense that balanced binary trees and sorting are fundamental for combinatorial algorithms in general. In this paper we will discuss and illustrate a number of these fundamental techniques of computational geometry. In most instances we give a worked out example of a problem solved by each of the techniques we discuss.

Historical note. The term "computational geometry" was originally coined by Robin Forrest [23] to denote the study of computational techniques in the realm of computer-aided geometric design. More recently, this term has been used to name a somewhat different field, in a way broader and in a way narrower than Forrest's conception, a field which is now considered part of theoretical computer science. This new use of the name "computational geometry," whose origin can be traced to Shamos [65], refers to the design and analysis of algorithms for all kinds of geometric problems, not necessarily in computer aided design. This is the sense in which the term will be used in this paper.