A relationship between Gale transforms and Voronoi diagrams (Q920405)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A relationship between Gale transforms and Voronoi diagrams |
scientific article |
Statements
A relationship between Gale transforms and Voronoi diagrams (English)
0 references
1990
0 references
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.)
0 references
Voronoi diagram
0 references
combinatorial geometry
0 references
computational geometry
0 references
power diagram
0 references
Gale transform
0 references