A relationship between Gale transforms and Voronoi diagrams

DOI10.1016/0166-218X(90)90108-OMaRDI QIDQ920405zbMATH OpenFDO

Authors Franz Aurenhammer

Publication date 1990

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(90)90108-O

zbMATH Keywords

combinatorial geometrycomputational geometryGale transformpower diagramVoronoi diagram

Mathematics Subject Classification ID

Other problems of combinatorial convexity (52A37) Gale and other diagrams (52B35) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

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

Recommendations

• scientific article; zbMATH DE number 4110184
• Using Gale transforms in computational geometry
• scientific article; zbMATH DE number 5734073
• Finite geometry and the Gale transform
• Some Applications of Affine Gale Diagrams to Polytopes with Few Vertices

Cites work

• A vector identity for the Dirichlet tessellation
• Angle Sums of Convex Polytopes.
• Diagrams for centrally symmetric polytopes
• Diagrams for Positive Bases
• Gale diagrams of convex polytopes and positive spanning sets of vectors
• scientific article; zbMATH DE number 3121295 (Why is no real title available?)
• scientific article; zbMATH DE number 4110184 (Why is no real title available?)
• scientific article; zbMATH DE number 3223483 (Why is no real title available?)
• scientific article; zbMATH DE number 3261280 (Why is no real title available?)
• Linear combinations from power domains
• Power Diagrams: Properties, Algorithms and Applications
• Recognizing Dirichlet tesselations
• Spherical complexes and nonprojective toric varieties
• The numbers of faces of simplicial polytopes

Cited in

(6)

• The Voronoi identity via the Laplace transform
• Improving continuity of Voronoi-based interpolation over Delaunay spheres
• Gale transforms and closed faces of infinite dimensional polytopes
• scientific article; zbMATH DE number 5734073 (Why is no real title available?)
• scientific article; zbMATH DE number 4110184 (Why is no real title available?)
• Using Gale transforms in computational geometry

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)