Geometric dominating sets - a minimum version of the No-Three-In-Line
Problem
O. Aichholzer, D. Eppstein, and E.-M. Hainzl
Abstract:
We consider a minimizing variant of the well-known No-Three-In-Line Problem,
the Geometric Dominating Set Problem: What is the smallest number of points
in an n×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 Ω(n2/3) points and provide a
constructive upper bound of size 2⌈n/2⌉. 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×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((nlogn)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.
Reference: O. Aichholzer, D. Eppstein, and E.-M. Hainzl.
Geometric dominating sets - a minimum version of the no-three-in-line problem.
Computational Geometry, 108:101-913, 2023.
root,
2022-09-22