Coloring points with respect to squares

DOI10.4230/LIPICS.SOCG.2016.5zbMATH Open1387.05076arXiv1512.01953OpenAlexW2737216762MaRDI QIDQ3132836FDOQ3132836

Authors: Eyal Ackerman, Balázs Keszegh, Máté Vizer 

Publication date: 30 January 2018

Abstract: We consider the problem of $2$-coloring geometric hypergraphs. Specifically, we show that there is a constant $m$ such that any finite set of points in the plane $mathcalSsubset{mathbbR}^2$ can be $2$-colored such that every axis-parallel square that contains at least $m$ points from $mathcalS$ 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 $2$-coloring points with respect to homothets of a fixed parallelogram.

Full work available at URL: https://arxiv.org/abs/1512.01953

Recommendations

• Coloring points with respect to squares
• Quasi‐random 2‐ colorings of point sets
• On coloring points with respect to rectangles
• Coloring Axis-Parallel Rectangles
• Coloring axis-parallel rectangles

zbMATH Keywords

polychromatic coloringcover-decomposabilitygeometric hypergraph coloringhomothets

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Hypergraphs (05C65)

Cited In (9)

• Matching points with squares
• Colorful strips
• Connecting colored point sets
• Coloring axis-parallel rectangles
• Coloring points with respect to squares
• Coloring Axis-Parallel Rectangles
• Quasi‐random 2‐ colorings of point sets
• On coloring points with respect to rectangles
• Colorful strips

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 Q3132836)