Blocking Delaunay triangulations

Given a set B of n black points in general position, we say that a set of white points W blocks B if in the Delaunay triangulation of [Formula: see text] there is no edge connecting two black points. We give the following bounds for the size of the smallest set W blocking B: (i) [Formula: see text]...

Descripción completa

Detalles Bibliográficos
Autores principales: Aichholzer, Oswin, Fabila-Monroy, Ruy, Hackl, Thomas, van Kreveld, Marc, Pilz, Alexander, Ramos, Pedro, Vogtenhuber, Birgit
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Elsevier 2013
Materias:
Article
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3587385/
https://www.ncbi.nlm.nih.gov/pubmed/23483043
http://dx.doi.org/10.1016/j.comgeo.2012.02.005
_version_ 1782261393217552384
author Aichholzer, Oswin
Fabila-Monroy, Ruy
Hackl, Thomas
van Kreveld, Marc
Pilz, Alexander
Ramos, Pedro
Vogtenhuber, Birgit
author_facet Aichholzer, Oswin
Fabila-Monroy, Ruy
Hackl, Thomas
van Kreveld, Marc
Pilz, Alexander
Ramos, Pedro
Vogtenhuber, Birgit
author_sort Aichholzer, Oswin
collection PubMed
description Given a set B of n black points in general position, we say that a set of white points W blocks B if in the Delaunay triangulation of [Formula: see text] there is no edge connecting two black points. We give the following bounds for the size of the smallest set W blocking B: (i) [Formula: see text] white points are always sufficient to block a set of n black points, (ii) if B is in convex position, [Formula: see text] white points are always sufficient to block it, and (iii) at least [Formula: see text] white points are always necessary to block a set of n black points.
format Online
Article
Text
id pubmed-3587385
institution National Center for Biotechnology Information
language English
publishDate 2013
publisher Elsevier
record_format MEDLINE/PubMed
spelling pubmed-35873852013-03-06 Blocking Delaunay triangulations Aichholzer, Oswin Fabila-Monroy, Ruy Hackl, Thomas van Kreveld, Marc Pilz, Alexander Ramos, Pedro Vogtenhuber, Birgit Comput Geom Article Given a set B of n black points in general position, we say that a set of white points W blocks B if in the Delaunay triangulation of [Formula: see text] there is no edge connecting two black points. We give the following bounds for the size of the smallest set W blocking B: (i) [Formula: see text] white points are always sufficient to block a set of n black points, (ii) if B is in convex position, [Formula: see text] white points are always sufficient to block it, and (iii) at least [Formula: see text] white points are always necessary to block a set of n black points. Elsevier 2013-02 /pmc/articles/PMC3587385/ /pubmed/23483043 http://dx.doi.org/10.1016/j.comgeo.2012.02.005 Text en © 2013 Elsevier B.V. https://creativecommons.org/licenses/by-nc-nd/3.0/ Open Access under CC BY-NC-ND 3.0 (https://creativecommons.org/licenses/by-nc-nd/3.0/) license
spellingShingle Article
Aichholzer, Oswin
Fabila-Monroy, Ruy
Hackl, Thomas
van Kreveld, Marc
Pilz, Alexander
Ramos, Pedro
Vogtenhuber, Birgit
Blocking Delaunay triangulations
title Blocking Delaunay triangulations
title_full Blocking Delaunay triangulations
title_fullStr Blocking Delaunay triangulations
title_full_unstemmed Blocking Delaunay triangulations
title_short Blocking Delaunay triangulations
title_sort blocking delaunay triangulations
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3587385/
https://www.ncbi.nlm.nih.gov/pubmed/23483043
http://dx.doi.org/10.1016/j.comgeo.2012.02.005
work_keys_str_mv AT aichholzeroswin blockingdelaunaytriangulations
AT fabilamonroyruy blockingdelaunaytriangulations
AT hacklthomas blockingdelaunaytriangulations
AT vankreveldmarc blockingdelaunaytriangulations
AT pilzalexander blockingdelaunaytriangulations
AT ramospedro blockingdelaunaytriangulations
AT vogtenhuberbirgit blockingdelaunaytriangulations

Ejemplares similares