Covering delaunay triangulation

Abstract

Given a set of $n$ black points $B$ in the plane, we want to place a set of red points $R$ so that every point in $B$ is a neighbor of at least one point in $R$ on the Delaunay triangulation of $B \cup R$. We give the following bounds. For the lower bound, we construct a set of $n$ black points so that we need at least $\frac{n}{4}$ red points. For the upper bound, we introduce an algorithm that covers all $n$ black points using at most $\frac{n}{2}$ red points, which improves the previous upper bound of $\frac{2n}{3}$. We also provide algorithms that use at most \frac{n}{3}$ red points, under two different constraints.