Ackerman, E. and Keszegh, Balázs and Vizer, Máté (2017) Coloring Points with Respect to Squares. DISCRETE AND COMPUTATIONAL GEOMETRY. pp. 1-28. ISSN 0179-5376 (In Press)
|
Text
1512.01953.pdf Download (658kB) | 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 of points in the plane (Formula presented.) can be 2-colored such that every axis-parallel square that contains at least m points from (Formula presented.) 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.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Self-coverability; Geometric hypergraph coloring; Cover-decomposability |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 11 Jul 2017 12:37 |
| Last Modified: | 11 Jul 2017 18:33 |
| URI: | http://real.mtak.hu/id/eprint/55849 |
Actions (login required)
 |
Edit Item |
