Coloring points with respect to squares (Q1688853)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Coloring points with respect to squares |
scientific article |
Statements
Coloring points with respect to squares (English)
0 references
11 January 2018
0 references
Let \(S\) be any set of points of a plane \(\mathbb{R}^2\) and suppose that we color points of \(S\) with two colors. The authors show that there exists a constant \(m<215\) such that if any (open or closed) parallelogram \(P\) of \(\mathbb{R}^2\) contains at least \(m\) points of \(S\), then there exists a 2-coloring of \(S\) such that \(P\) contains points of both colors. The proof is constructive and provides a polynomial time algorithm for a desired 2-coloring. It is also shown that with this method one can prove a similar result for triangles. In the introduction the connection to geometric hypergraphs is presented which covers above mention model.
0 references
plane
0 references
2-coloring
0 references
parallelogram
0 references
hypergraph
0 references
0 references