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~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 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 2$. For arbitrary $n$ the currently best upper bound remains the obvious $2n$. Finally, we discuss some further variations of the problem.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 37th European Workshop on Computational Geometry (EuroCG$$2021) |
| Place of Publication | St. Petersburg, Germany |
| Pages | 17:1-17:7 |
| Number of pages | 7 |
| Publication status | Published - 2021 |
Fields of Expertise
- Information, Communication & Computing