Geometric Dominating Sets

Oswin Aichholzer, David Eppstein, Eva-Maria Hainzl

Research output: Working paperPreprint

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 pr
Original languageEnglish
PublisherarXiv
DOIs
Publication statusPublished - 24 Mar 2022

Keywords

  • cs.CG
  • math.CO

Fields of Expertise

  • Information, Communication & Computing

Fingerprint

Dive into the research topics of 'Geometric Dominating Sets'. Together they form a unique fingerprint.

Cite this