The geometric stability of Voronoi diagrams in normed spaces which are not uniformly convex
From MaRDI portal
Publication:6237760
arXiv1212.1094MaRDI QIDQ6237760FDOQ6237760
Authors: Daniel Reem 
Publication date: 4 December 2012
Abstract: The Voronoi diagram is a geometric object which is widely used in many areas. Recently it has been shown that under mild conditions Voronoi diagrams have a certain continuity property: small perturbations of the sites yield small perturbations in the shapes of the corresponding Voronoi cells. However, this result is based on the assumption that the ambient normed space is uniformly convex. Unfortunately, simple counterexamples show that if uniform convexity is removed, then instability can occur. Since Voronoi diagrams in normed spaces which are not uniformly convex do appear in theory and practice, e.g., in the plane with the Manhattan (ell_1) distance, it is natural to ask whether the stability property can be generalized to them, perhaps under additional assumptions. This paper shows that this is indeed the case assuming the unit sphere of the space has a certain (non-exotic) structure and the sites satisfy a certain "general position" condition related to it. The condition on the unit sphere is that it can be decomposed into at most one "rotund part" and at most finitely many non-degenerate convex parts. Along the way certain topological properties of Votonoi cells (e.g., that the induced bisectors are not "fat") are proved.
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Geometry and structure of normed linear spaces (46B20) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Miscellaneous applications of functional analysis (46N99)
This page was built for publication: The geometric stability of Voronoi diagrams in normed spaces which are not uniformly convex
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237760)
