A relationship between Gale transforms and Voronoi diagrams (Q920405)

Gale transforms of point sets are used to reveal certain combinatorial properties of point sets and convex polytopes. Moreover, recently they have found applications in computational geometry, too [the author, Lect. Notes Comput. Sci. 333, 202-216 (1988; Zbl 0677.68120)]. The reviewed paper describes a relationship between Gale transforms and power diagrams (generalizations of Voronoi diagrams) of a point set. This gives a method to construct Gale transforms. In the two-dimensional case the transition from the power diagram to a Gale transform takes linear time. (Two-dimensional power diagrams can be constructed in \(O(n \log n)\) time.)