Connecting red cells in a bichromatic Voronoi diagram

Hernández Peñalver, Gregorio and Abellanas Oar, Manuel and Bajuelos Domínguez, Antonio Leslie and Canales Cano, Santiago and Claverol, Merce and Matos, Ines (2012). Connecting red cells in a bichromatic Voronoi diagram. In: "XIV Spanish Meeting on Computacional Geometry", 27/06/2011 - 30/06/2011, Alcalá de Henares, Madrid. ISBN 978-3-642-34190-8. pp. 173-176.

Description

Title: Connecting red cells in a bichromatic Voronoi diagram
Author/s:
  • Hernández Peñalver, Gregorio
  • Abellanas Oar, Manuel
  • Bajuelos Domínguez, Antonio Leslie
  • Canales Cano, Santiago
  • Claverol, Merce
  • Matos, Ines
Item Type: Presentation at Congress or Conference (Article)
Event Title: XIV Spanish Meeting on Computacional Geometry
Event Dates: 27/06/2011 - 30/06/2011
Event Location: Alcalá de Henares, Madrid
Title of Book: Computational Geometry
Date: 2012
ISBN: 978-3-642-34190-8
Volume: 7579
Subjects:
Freetext Keywords: Weighted Voronoi diagrams, Bicolour Points, Diagrama ponderado Voronoi, Puntos bicolor.
Faculty: Facultad de Informática (UPM)
Department: Matemática Aplicada
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (732kB) | Preview

Abstract

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 wR such that the union of the red Voronoi cells in the weighted Voronoi diagram of S is a connected set. The problem is solved for the multiplicatively-weighted Voronoi diagram in O((n+m)^2 log(nm)) time and for the additively-weighted Voronoi diagram in O(nmlog(nm)) time.

More information

Item ID: 19279
DC Identifier: http://oa.upm.es/19279/
OAI Identifier: oai:oa.upm.es:19279
Official URL: http://link.springer.com/chapter/10.1007%2F978-3-642-34191-5_20
Deposited by: Memoria Investigacion
Deposited on: 24 Sep 2013 17:13
Last Modified: 21 Apr 2016 17:32
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM