Connecting red cells in a bicolour Voronoi diagram Conference

Abellanas, M, Bajuelos, AL, Canales, S et al. (2012). Connecting red cells in a bicolour Voronoi diagram . EURO-PAR 2011 PARALLEL PROCESSING, PT 1, 7579 LNCS 210-219. 10.1007/978-3-642-34191-5_20

cited authors

  • Abellanas, M; Bajuelos, AL; Canales, S; Claverol, M; Hernández, G; Matos, I

authors

abstract

  • Let S be a set of n + m sites, of which n are red and have weight w R , and m are blue and weigh w B. 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 multiplicatively-weighted 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. © 2012 Springer-Verlag.

publication date

  • November 30, 2012

published in

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 13

start page

  • 210

end page

  • 219

volume

  • 7579 LNCS