Voronoi cells via linear inequality systems
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10045/36009
Title: | Voronoi cells via linear inequality systems |
---|---|
Authors: | Goberna, Miguel A. | Rodríguez Álvarez, Margarita | Vera de Serio, Virginia N. |
Research Group/s: | Laboratorio de Optimización (LOPT) |
Center, Department or Service: | Universidad de Alicante. Departamento de Estadística e Investigación Operativa |
Keywords: | Voronoi cells | Voronoi diagrams | Linear inequality systems | Locally polyhedral systems | Quasipolyhedral sets |
Knowledge Area: | Estadística e Investigación Operativa |
Issue Date: | 1-Apr-2012 |
Publisher: | Elsevier |
Citation: | Linear Algebra and its Applications. 2012, 436(7): 2169-2186. doi:10.1016/j.laa.2011.12.016 |
Abstract: | 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. |
Sponsor: | This work has been supported by MICINN of Spain, Grant MTM2008-06695-C03-01/03 and SECTyP-UNCuyo, Argentina. |
URI: | http://hdl.handle.net/10045/36009 |
ISSN: | 0024-3795 (Print) | 1873-1856 (Online) |
DOI: | 10.1016/j.laa.2011.12.016 |
Language: | eng |
Type: | info:eu-repo/semantics/article |
Peer Review: | si |
Publisher version: | http://dx.doi.org/10.1016/j.laa.2011.12.016 |
Appears in Collections: | INV - LOPT - Artículos de Revistas |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
2012_Goberna_etal_LAA.pdf | Preprint (acceso abierto) | 228,46 kB | Adobe PDF | Open Preview |
2012_Goberna_etal_LAA-final.pdf | Versión final (acceso restringido) | 338,38 kB | Adobe PDF | Open Request a copy |
Items in RUA are protected by copyright, with all rights reserved, unless otherwise indicated.