ABSTRACT
This chapter presents several complexes used in subsequent chapters. Voronoi diagrams are among the oldest geometric complexes studied; they are unbounded polyhedral complexes that associate each point in space with the closest site in a fixed set of sites-for instance, indicating for every point in town the nearest post office, as illustrated in Figure 7.1. Voronoi diagrams arise in the study of natural phenomena such as crystal formation, meteorology, computational chemistry, condensed matter physics, and epidemiology. Historically, they have been rediscovered several times and are also known as Dirichlet tessellations, Thiessen polygons, and Wigner-Seitz cells. They are the natural combinatorial duals of Delaunay subdivisions. In later chapters, they play important roles in ensuring the topological correctness of algorithms for meshing curved surfaces.
