06112263

j

06112263 Aichholzer, Oswin Fabila-Monroy, Ruy Hackl, Thomas van Kreveld, Marc Pilz, Alexander Ramos, Pedro Vogtenhuber, Birgit Blocking Delaunay triangulations. Comput. Geom. 46, No. 2, 154-159 (2013). 2013 Elsevier Science B.V. (North-Holland), Amsterdam EN proximity graphs Delaunay graph graph drawing witness graphs

doi:10.1016/j.comgeo.2011.06.004

Summary: 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 \cup 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) $3n/2$ white points are always sufficient to block a set of $n$ black points, (ii) if $B$ is in convex position, $5n/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.