Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2013 Feb;46(2):154-159.
doi: 10.1016/j.comgeo.2012.02.005.

Blocking Delaunay triangulations

Oswin Aichholzer  1 , Ruy Fabila-Monroy, Thomas Hackl, Marc van Kreveld, Alexander Pilz, Pedro Ramos, Birgit Vogtenhuber
Affiliations

Blocking Delaunay triangulations

Oswin Aichholzer et al. Comput Geom. 2013 Feb.

Abstract

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.

Keywords: Delaunay graph; Graph drawing; Proximity graphs; Witness graphs.

PubMed Disclaimer

Figures

Fig. 1
Fig. 1
Blocking a black point by placing two white points in its Voronoi cell.
Fig. 2
Fig. 2
A (14,5,6)-cut and the retriangulated subset. (Colored vertices are shown (half) encircled For the complete color version in this figure, the reader is referred to the web version of this article.)
Fig. 3
Fig. 3
The two cases for a convex set: removing an ear (a), and removing an inner triangle with two incident ears (b). (Colored vertices are shown (half) encircled and colored edges are marked with an “x”. For the complete color version in this figure, the reader is referred to the web version of this article.)
Fig. 4
Fig. 4
Euros proving a lower bound of n white points.
See this image and copyright information in PMC

References

    1. S.I. Ahmed, M. Hasan, A. Sopan, Vindictive Voronoi games and stabbing Delaunay circles, in: Proc. ISVD 2010, pp. 124–131.
    1. Ahn H.-K., Cheng S.-W., Cheong O., Golin M., van Oostrum R. Competitive facility location: the Voronoi game. Theoretical Computer Science. 2004;310:457–467.
    1. Aronov B., Dulieu M., Hurtado F. Witness (Delaunay) graphs. Computational Geometry: Theory and Applications. 2011;44:329–344.
    1. B. Aronov, M. Dulieu, F. Hurtado, Witness Gabriel graphs, Computational Geometry: Theory and Applications, in press, doi:10.1016/j.comgeo.2011.06.004. - DOI
    1. M. de Berg, D. Gerrits, A. Khosravi, I. Rutter, C. Tsirogiannis, A. Wolff, How Alexander the Great brought the Greeks together while inflicting minimal damage to the Barbarians, in: Proc. 26th European Workshop on Computational Geometry, 2010, pp. 73–76.

LinkOut - more resources