Blocking Delaunay triangulations
Oswin Aichholzer, Ruy Fabila‐Monroy, Thomas Hackl, Marc J. van Kreveld, Alexander Pilz, Pedro A. Ramos, Birgit Vogtenhuber · Computational Geometry · 2012
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 B ∪ W there is no edge connecting two black points. We give the following bounds for the size of the smallest set W blocking B : (i) 3 n / 2 white points are always sufficient to block a set of n black points, (ii) if B is in convex position, 5 n / 4 white points are always sufficient to block it, and (iii) at least n − 1 white points are always necessary to block a set of n black points.