[Zurück]

E. Hainzl, O. Aichholzer, D. Eppstein:
"Geometric Dominating Sets - A Minimum Version of the No-Three-In-Line Problem.";
in: "Proceedings of the 37th European Workshop on Computational Geometry", Proceedings of the 37th European Workshop on Computational Geometry, St. Petersburg, Russia, 2021, S. 122 - 128.

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

https://publik.tuwien.ac.at/files/publik_299296.pdf