Coloring points with respect to squares
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.
- Coloring axis-parallel rectangles
- Coloring half-planes and bottomless rectangles
- Concrete and abstract Voronoi diagrams
- Conflict-free coloring and its applications
- Conflict-free coloring for rectangle ranges using \(O(n ^{.382})\) colors
- Conflict-free coloring of points and simple regions in the plane
- Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set
- Convex polygons are cover-decomposable
- Convex polygons are self-coverable
- Covering the plane with convex polygons
- Decomposition of multiple coverings into many parts
- Decomposition of multiple coverings into more parts
- Delaunay graphs of point sets in the plane with respect to axis‐parallel rectangles
- scientific article; zbMATH DE number 1520171 (Why is no real title available?)
- scientific article; zbMATH DE number 2209737 (Why is no real title available?)
- Indecomposable Coverings
- Indecomposable coverings with concave polygons
- Indecomposable coverings with homothetic polygons
- Making Octants Colorful and Related Covering Decomposition Problems
- Making triangles colorful
- More on decomposing coverings by octants
- Multiple coverings of the plane with triangles
- Octants are cover-decomposable
- Octants are cover-decomposable into many coverings
- On coloring points with respect to rectangles
- On the stretch factor of convex Delaunay graphs
- Optimally decomposing coverings with translates of a convex polygon
- Polychromatic coloring for half-planes
- Proper coloring of geometric hypergraphs
- Survey on decomposition of multiple coverings
- Topological hypergraphs
- On coloring points with respect to rectangles
- Coloring Delaunay-edges and their generalizations
- Coloring intersection hypergraphs of pseudo-disks
- Coloring points with respect to squares
- scientific article; zbMATH DE number 437473 (Why is no real title available?)
- Colorful strips
- Quasi‐random 2‐ colorings of point sets
- Coloring intersection hypergraphs of pseudo-disks
- Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
- Coloring Axis-Parallel Rectangles
- Polychromatic colorings of unions of geometric hypergraphs
- Colouring bottomless rectangles and arborescences
- Colorful strips
- Coloring hypergraphs defined by stabbed pseudo-disks and ABAB-free hypergraphs
- Polychromatic colorings of geometric hypergraphs via shallow hitting sets
- Realizing an m-uniform four-chromatic hypergraph with disks
- Polychromatic coloring of tuples in hypergraphs
- Connecting colored point sets
- A note on balanced colourings for lattice points
- Coloring axis-parallel rectangles
This page was built for publication: Coloring points with respect to squares
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688853)
