DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2016.5

Coloring Points with Respect to Squares

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

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract

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.

Cite as

Eyal Ackerman, Balázs Keszegh, and Máté Vizer. Coloring Points with Respect to Squares. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2016.5,
  author =	{Ackerman, Eyal and Keszegh, Bal\'{a}zs and Vizer, M\'{a}t\'{e}},
  title =	{{Coloring Points with Respect to Squares}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.5},
  URN =		{urn:nbn:de:0030-drops-58972},
  doi =		{10.4230/LIPIcs.SoCG.2016.5},
  annote =	{Keywords: Geometric hypergraph coloring, Polychromatic coloring, Homothets, Cover-decomposability}
}

Search Results

Documents authored by Vizer, Máté

Coloring Points with Respect to Squares

Abstract

Cite as

Thanks for your feedback!

Could not send message