1 Search Results for "Vizer, M�t�"

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-dev.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}
}
  • Refine by Author
  • 1 Ackerman, Eyal
  • 1 Keszegh, Balázs
  • 1 Vizer, Máté

  • Refine by Classification

  • Refine by Keyword
  • 1 Cover-decomposability
  • 1 Geometric hypergraph coloring
  • 1 Homothets
  • 1 Polychromatic coloring

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact