Connecting Red Cells in a Bicolour Voronoi Diagram
| Autor: | Abellanas, Manuel, Bajuelos, Antonio L., Canales, Santiago, Claverol Aguas, Mercè, Hernández, Gregorio, Pereira de Matos, Inés |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV, Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya. DCCG - Grup de recerca en geometria computacional, combinatoria i discreta |
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
Voronoi polygons
Astrophysics::Solar and Stellar Astrophysics Voronoi Polígons de Astrophysics::Cosmology and Extragalactic Astrophysics Matemàtiques i estadística::Geometria::Geometria computacional [Àrees temàtiques de la UPC] Computer Science::Computational Geometry Astrophysics::Galaxy Astrophysics Geometria computacional Geometry --Data processing |
| Zdroj: | UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) Recercat. Dipósit de la Recerca de Catalunya instname |
| Popis: | Let S be a set of n + m sites, of which n are red and have weight wR, and m are blue and weigh wB. The objective of this paper is to calculate the minimum value of the red sites’ weight such that the union of the red Voronoi cells in the weighted Voronoi diagram of S is a connected region. This problem is solved for the multiplicativelyweighted Voronoi diagram in O((n+m)2 log(nm)) time and for both the additively-weighted and power Voronoi diagram in O(nmlog(nm)) time |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|