A relationship between Gale transforms and Voronoi diagrams

From MaRDI portal





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.)











This page was built for publication: A relationship between Gale transforms and Voronoi diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q920405)