2026-08-10T18:26:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5897 2024-03-06T10:37:14Z ddc:004 open_access

Coloring Points with Respect to Squares Ackerman, Eyal Keszegh, Balázs Vizer, Máté Geometric hypergraph coloring Polychromatic coloring Homothets Cover-decomposability We consider the problem of 2-coloring geometric hypergraphs. Specifically, we show that there is a constant m such that any finite set S of points in the plane can be 2-colored such that every axis-parallel square that contains at least m points from S contains points of both colors. Our proof is constructive, that is, it provides a polynomial-time algorithm for obtaining such a 2-coloring. By affine transformations this result immediately applies also when considering homothets of a fixed parallelogram. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eyal Ackerman and Balázs Keszegh and Máté Vizer 2016 Is Part Of LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2016.5 urn:nbn:de:0030-drops-58972 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.5 eng https://creativecommons.org/licenses/by/3.0/legalcode