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.
Voronoi 다이어그램에서 모든 경쟁사의 점포를 이웃하게 만들면서, 자기 점포의 수를 최소화 하는 문제를 이 논문에서 다루고자 한다. n개의 파란 점들의 집합이 있고, 만약 검은 점들의 집합과 빨간 점들의 집합으로 이루어진 Delaunay 삼각 분할에서 모든 파란 점들이 빨간 점들과 연결이 되어있다면, 우리는 이것을 빨간 점들의 집합이 파란 점들을 덮는다고 말한다. 여기서 우리는 모든 파란 점들의 집합을 최소한의 빨간 점들의 수로 덮는 것을 목표로 하는 문제로 바꿀 수 있다. 우리는 정삼각형들의 꼭지점과 그 중심으로 이루어진 n/4 하계 예제를 보이고 이것을 증명하였다. 우리는 상계가 2n/3인 이전 결과보다 좋은 n/2인 결과를 완전정합을 사용하여서 증명하였다. 또, 우리는 Delaunay 삼각 분할에서 이웃한 두 변에 있는 세 개의 점들을 항상 덮을 수 있다는 성질 또한 소개하였다. 이 성질을 이용하여서 두 개의 다른 제약조건이 있는 상계가 n/3인 두 가지 방법을 제시하고 증명하였다.
