Voronoi diagrams and Delaunay triangulations (Q2854053)

Voronoi diagrams (VD) and their dual Delaunay tesselations (DT) are now well established and studied geometric constructs with an explosively growing body of theory and applications. This book by three of the very active players in the field is an appreciated attempt at giving a wide range (necessarily incomplete) theoretical overview of the current state of the art about their many variant forms and corresponding structural properties, mainly from the computational geometric point of view, emphasizing the search for low complexity algorithmic construction approaches. Starting out with the easier euclidean plane setting, it quickly moves on to many often much harder extensions in terms of types of sites, distance or influence function, dimension etc. Most results and techniques are proven, though the arguments are sometimes only sketched or hinted at when calling for too many specialized details or lengtly developments, but always amply referenced out of a bibliography of over 700 entries, resulting at places in survey paper style. In this sense the work clearly fills a gap in the available literature of booksize, and forms at the same time a valuable entry to the field for interested students, lecturers and scholars with a good background in classical vector space geometry and complexity analysis of algorithms, but also welcome as a broad source of ideas and pointers to the expert research community for theoretical developments.NEWLINENEWLINEBelow we list a selected few topics one finds developed in the book.NEWLINENEWLINEAfter a very short introduction to the history, definition and basic properties of the standard VD/DT in the plane (more advanced characterization and optimality properties come later), four prototypic algorithmic approaches are described: a randomized incremental (or online) method constructs DT in expected optimal time and space, a plane sweep method, a divide and conquer approach recursively based on split and merge steps, and a lifting to 3D that transforms VD into a convex hull, all allow to construct VD in worst case optimal time and space. Most of the coming more general settings will allow to be efficiently solved by adapting at least one of these approaches.NEWLINENEWLINESites should not necessarily be points, but may be fixed size subsets of a point set, leading to higher order VD, strongly related to hyperplane arrangements. They may be other objects like line segments that yield curved line diagrams, for which linear alternatives exist like the straight skeleton, or even curved objects. In dimension above 2 the more general notion of Power diagram (PD) may be lifted using an additional dimension to become equivalent to a convex hull, while any simplicial complex satisfying a regularity property is dual to such a PD. On the application side, for any finite set of sites and any continuous distribution on the unit cube there exists a power diagram that partitions the cube into power cells of prescribed measures which may be obtained by an efficient incremental algorithm.NEWLINENEWLINEMore general spaces in which Voronoi diagrams may be of interest includes geodesic surfaces and convex (or Minkowski) distances. Care must be taken with the latter since several DT notions exist: the often algorithmically essential so-called empty `circle' property of DT no longer holds. Bisectors for any convex distance are `nice' however, retaining sufficient properties to generalize VD construction methods, leading to the definition of even more general abstract (or axiomatically defined) Voronoi spaces where the corresponding VD may be obtained both incrementally and by divide and conquer. The introduction of weights to the points, included either additively or multiplicatively in the distances, complcate matters, but not overly so.NEWLINENEWLINEThe chapter on `applications' is to be understood as other mathematical questions solvable by way of VD- and/or DT-like constructs. For the many applications in other sciences the reader is referred to several other existing sources. The most basic application is of course the post office problem asking to determine for an arbitrary query point what is the nearest among the given sites, answered by locating the point in their VD. Similar are the closest pair and largest empty or smallest enclosing `circle' problems. The minimum spanning tree is a subtree of DT, that is also of direct use for certain shape reconstruction, skeleton and spanner constructions (allowing quick approximate shortest path calculations). Some problems in optimal clustering and motion planning are also treated.NEWLINENEWLINEA miscellanea chapter surveys some dynamic aspects, facility location questions like maximizing the Voronoi cell of an incoming site or as a game where sites may be moved, zone diagrams and VD/DT structures on graphs. The book ends with a short discussion of the curse of dimensionality leading to the difficulty and/or inefficiency of the previously discussed techniques in high dimensional spaces and gives a few paths to some recent alternative approaches for attacking distance related questions in such cases, followed by a short list of related topics that were not discussed and a few important problems remaining open at the time of writing.