Axioms and Hulls - Lecture Notes in Computer Science 606 (Paperback)

One way to advance the science of computational geometry is

to make a comprehensive study of fundamental operations that

are used in many different algorithms. This monograph

attempts such an investigation in the case of two basic

predicates: the counterclockwise relation pqr, which states

that the circle through points (p, q, r) is traversed

counterclockwise when we encounter the points in cyclic

order p, q, r, p,...; and the incircle relation pqrs, which

states that s lies inside that circle if pqr is true, or

outside that circle if pqr is false. The author, Donald

Knuth, is one of the greatest computer scientists of our

time. A few years ago, he and some of his students were

looking at amap that pinpointed the locations of about 100

cities. They asked, "Which ofthese cities are neighbors of

each other?" They knew intuitively that some pairs of cities

were neighbors and some were not; they wanted to find a

formal mathematical characterization that would match their

intuition.This monograph is the result.