Geometric Dominating Sets

Abstract

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 $\Omega (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.

Cited by in corpus (1)

• The extensible No-Three-In-Line problem