论文标题
几何主导集
Geometric Dominating Sets
论文作者
论文摘要
我们考虑了众所周知的\ emph {no-thre-in-in-in-in-in-emph {几何主导套件问题}的最小化变体：$ n \ times n $〜网格中最小数量的点是多少，以使每个网格点都在共同的线上，与两个点相处有两个点？我们显示$ω（n^{2/3}）$点的下限，并提供了$ 2 \ lceil n/2 \ rceil $的建设性上限。如果要求主体设置的点必须处于一般位置，我们为大小的网格提供最佳解决方案，最高为$ 12 \ times 12 $。对于任意$ n $，目前最佳的上限最佳位置仍然是显而易见的$ 2N $。最后，我们在离散的圆环上讨论了问题，在该问题中，我们证明了$ o（（n \ log n）^{1/2}）$的上限。对于$ n $偶数或3个倍数，我们甚至可以显示4个恒定的上限。我们还提到了许多开放问题和问题的进一步变化。
We consider a minimizing variant of the well-known \emph{No-Three-In-Line Problem}, the \emph{Geometric Dominating Set Problem}: What is the smallest number of points in an $n\times n$~grid such that every grid point lies on a common line with two of the points in the set? We show a lower bound of $Ω(n^{2/3})$ points and provide a constructive upper bound of size $2 \lceil n/2 \rceil$. If the points of the dominating sets are required to be in general position we provide optimal solutions for grids of size up to $12 \times 12$. For arbitrary $n$ the currently best upper bound for points in general position remains the obvious $2n$. Finally, we discuss the problem on the discrete torus where we prove an upper bound of $O((n \log n)^{1/2})$. For $n$ even or a multiple of 3, we can even show a constant upper bound of 4. We also mention a number of open questions and some further variations of the problem.
