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