Computational Geometry II
D Lee · Chapman & Hall/CRC applied algorithms and data structures series · 2009
Introduction This is a follow up on the previous Chapter dealing with geometric problems and their efficient solutions. The classes of problems that we address in this Chapter include proximity, optimization, intersection, searching, point location, and some discussions of geometric software that is under development. 2 Proximity Geometric problems pertaining to the questions of how close two geometric entities are among a collection of objects or how similar two geometric patterns match each other abound. For example, in pattern classification and clustering, features that are similar according to some metric, are to be clustered in a group. The two aircrafts that are closest at any time instant in the air space will have the largest likelihood of collision with each other. In some cases one may be interested in how far apart or how dissimilar the objects are. Some of