Concrete and abstract Voronoi diagrams (Q1188589)

Let S be a finite set of objects \(p_ i\) in a space M. A partition of M into regions \(R(p_ i,S)\) such that \(R(p_ i,S)\) contains all points of M that are closer to \(p_ i\) than to any other object \(p_ j\) in S is called Voronoi diagram of S. The Voronoi diagram is one of the most useful data structures in computational geometry, with applications in many other areas of science as well. Known more than one hundred years ago, the Voronoi diagram was introduced to computer science in 1975 and since then studied and used in number of proximity problems. However, in many situations ``classical'' Voronoi diagrams based on the notion of distance does not provide satisfying solution due to various obstacles in the space M or, more generally, regions to whose interior different metrics apply. Rolf Klein overcomes these difficulties by introducing abstract Voronoi diagrams, based on the concept of bisecting curves instead of the notions of sites and distances. Then, Voronoi regions R(p,S) can be defined in the usual way, by intersecting halfplanes. Investigation of abstract Voronoi diagrams and efficient algorithms for constructing them together form the core of his book. The book starts with excellent brief history of Voronoi diagrams, followed by a survey of known approaches and algorithms. Then a definition of the Voronoi diagram for general metrics and a definition of a class of ``nice'' metrics are given. Then abstract Voronoi diagrams are introduced and investigated in order to prove that this approach does in fact lead to a unification of the theory. Next chapter deals with efficient algorithms for constructing abstract Voronoi diagrams. As these algorithms are based on the existence of ``acyclic'' partition, in the last chapter sufficient criteria for the existence of such partitions are given. Outline of open problems together with nice list of references finishes this useful book.