<div class="csl-bib-body">
<div class="csl-entry">Aichholzer, O., Eppstein, D., & Hainzl, E.-M. (2021). Geometric dominating sets - a minimum version of the No-Three-In-Line Problem. In <i>Proceedings of the 37th European Workshop on Computational Geometry</i>. 37th European Workshop on Computational Geometry (EuroCG2021), St.Petersburg, Russian Federation (the). http://hdl.handle.net/20.500.12708/41797</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/41797
-
dc.description.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
dc.language.iso
en
-
dc.subject
Computer Science Applications
-
dc.subject
Computational Mathematics
-
dc.subject
Computational Theory and Mathematics
-
dc.subject
Geometry and Topology
-
dc.subject
Control and Optimization
-
dc.title
Geometric dominating sets - a minimum version of the No-Three-In-Line Problem
en
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.contributor.affiliation
Graz University of Technology, Austria
-
dc.contributor.affiliation
University of California, Irvine, United States of America (the)
-
dc.type.category
Abstract Book Contribution
-
tuw.booktitle
Proceedings of the 37th European Workshop on Computational Geometry
-
tuw.publication.orgunit
E104-05 - Forschungsbereich Kombinatorik und Algorithmen
-
dc.description.numberOfPages
7
-
tuw.author.orcid
0000-0002-2364-0583
-
tuw.event.name
37th European Workshop on Computational Geometry (EuroCG2021)
-
tuw.event.startdate
07-04-2021
-
tuw.event.enddate
09-04-2021
-
tuw.event.online
Online
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
St.Petersburg
-
tuw.event.country
RU
-
tuw.presentation.online
Online
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1010
-
wb.facultyfocus
Diskrete Mathematik und Geometrie
de
wb.facultyfocus
Discrete Mathematics and Geometry
en
wb.facultyfocus.faculty
E100
-
item.cerifentitytype
Publications
-
item.languageiso639-1
en
-
item.fulltext
no Fulltext
-
item.openairetype
conference paper
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.grantfulltext
restricted
-
crisitem.author.dept
Graz University of Technology
-
crisitem.author.dept
E104-05 - Forschungsbereich Kombinatorik und Algorithmen
-
crisitem.author.orcid
0000-0002-2364-0583
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie
