Coloring points with respect to squares

DOI10.4230/LIPICS.SOCG.2016.5MaRDI QIDQ3132836zbMATH OpenOpenAlexFDO

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

Publication date 30 January 2018

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

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)

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.

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

Cited in

(9)

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

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)