Geometric Dominating Sets - A Minimum Version of the No-Three-In-Line Problem

Oswin Aichholzer, David Eppstein, Eva-Maria Hainzl

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


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 languageEnglish
Title of host publicationProceedings of the 37th European Workshop on Computational Geometry (EuroCG$$2021)
Place of PublicationSt. Petersburg, Germany
Number of pages7
Publication statusPublished - 2021

Fields of Expertise

  • Information, Communication & Computing

Cite this