Record link: 
http://hdl.handle.net/20.500.12708/41797
-
Title: 
Geometric dominating sets - a minimum version of the No-Three-In-Line Problem
en
Citation: 
Aichholzer, O., Eppstein, D., & Hainzl, E.-M. (2021). Geometric dominating sets - a minimum version of the No-Three-In-Line Problem. In Proceedings of the 37th European Workshop on Computational Geometry. 37th European Workshop on Computational Geometry (EuroCG2021), St.Petersburg, Russian Federation (the). http://hdl.handle.net/20.500.12708/41797
-
Publication Type: 
Inproceedings - Abstract Book Contribution
en
Language: 
English
-
Authors: 
Aichholzer, Oswin 
Eppstein, David 
Hainzl, Eva-Maria 
-
Organisational Unit: 
E104-05 - Forschungsbereich Kombinatorik und Algorithmen 
-
Published in: 
Proceedings of the 37th European Workshop on Computational Geometry 
-
Date (published): 
2021
-
Event name: 
37th European Workshop on Computational Geometry (EuroCG2021) 
-
Event date: 
7-Apr-2021 - 9-Apr-2021
-
Event place: 
St.Petersburg, Russian Federation (the)
-
Number of Pages: 
7
-
Keywords: 
Computer Science Applications; Computational Mathematics; Computational Theory and Mathematics; Geometry and Topology; Control and Optimization
-
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 Ω(n 2/3) points and provide a constructive upper bound of size 2dn/2e. 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 remains the obvious 2n. Finally, we discuss some further variations of the problem.
en
Science Branch: 
Mathematik
-
Appears in Collections:
Conference Paper

Show full item record

Google ScholarTM

Check