Voronoi cells via linear inequality systems
Contribuinte(s) |
Universidad de Alicante. Departamento de Estadística e Investigación Operativa Laboratorio de Optimización (LOPT) |
---|---|
Data(s) |
11/03/2014
11/03/2014
01/04/2012
|
Resumo |
The theory and methods of linear algebra are a useful alternative to those of convex geometry in the framework of Voronoi cells and diagrams, which constitute basic tools of computational geometry. As shown by Voigt and Weis in 2010, the Voronoi cells of a given set of sites T, which provide a tesselation of the space called Voronoi diagram when T is finite, are solution sets of linear inequality systems indexed by T. This paper exploits systematically this fact in order to obtain geometrical information on Voronoi cells from sets associated with T (convex and conical hulls, tangent cones and the characteristic cones of their linear representations). The particular cases of T being a curve, a closed convex set and a discrete set are analyzed in detail. We also include conclusions on Voronoi diagrams of arbitrary sets. This work has been supported by MICINN of Spain, Grant MTM2008-06695-C03-01/03 and SECTyP-UNCuyo, Argentina. |
Identificador |
Linear Algebra and its Applications. 2012, 436(7): 2169-2186. doi:10.1016/j.laa.2011.12.016 0024-3795 (Print) 1873-1856 (Online) http://hdl.handle.net/10045/36009 10.1016/j.laa.2011.12.016 |
Idioma(s) |
eng |
Publicador |
Elsevier |
Relação |
http://dx.doi.org/10.1016/j.laa.2011.12.016 |
Direitos |
info:eu-repo/semantics/restrictedAccess |
Palavras-Chave | #Voronoi cells #Voronoi diagrams #Linear inequality systems #Locally polyhedral systems #Quasipolyhedral sets #Estadística e Investigación Operativa |
Tipo |
info:eu-repo/semantics/article |