Ackerman, E. and Keszegh, Balázs and Vizer, Máté (2016) Coloring points with respect to squares. In: Coloring Points with Respect to Squares. Leibniz International Proceedings in Informatics (LIPIcs) . Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, 5.1-5.16. ISBN 978-3-95977-009-5
|
Text
1512.01953.pdf Download (314kB) | Preview |
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. © Eyal Ackerman, Balázs Keszegh, and Máté Vizer.
| Item Type: | Book Section |
|---|---|
| Additional Information: | N1 Funding Details: 267165, ERC, European Research Council A4 et al.; National Science Foundation (NSF); Princeton University; The Center for Geometry and its Applications (SRC-GAIA); The Fields Institute for Research in Mathematical Sciences; Tufts University |
| Uncontrolled Keywords: | Computational geometry; Polynomial-time algorithms; Polychromatic colorings; Hypergraph coloring; Geometric hypergraphs; Finite set; Decomposability; Affine transformations; Polynomial approximation; GEOMETRY; Algorithms; Polychromatic coloring; Homothets; Geometric hypergraph coloring; Cover-decomposability |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 03 Jan 2017 19:03 |
| Last Modified: | 03 Jan 2017 19:03 |
| URI: | http://real.mtak.hu/id/eprint/44225 |
Actions (login required)
 |
Edit Item |
