Name
Abstract | ||
|---|---|---|
We consider the problem of 2-coloring geometric hypergraphs. Specifically, we show that there is a constant such that any finite set of points in the plane can be 2-colored such that every axis-parallel square that contains at least points from 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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/s00454-017-9902-y | Discrete & Computational Geometry |
Keywords | Field | DocType |
Geometric hypergraph coloring,Cover-decomposability,Self-coverability,52C15 (05C15) | Affine transformation,Discrete mathematics,Combinatorics,Parallelogram,Finite set,Constructive,Constraint graph,Mathematics | Conference |
Volume | Issue | ISSN |
58 | 4 | 0179-5376 |
Citations | PageRank | References |
4 | 0.75 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Eyal Ackerman | 1 | 188 | 19.80 |
| Balázs Keszegh | 2 | 156 | 24.36 |
| Máté Vizer | 3 | 27 | 14.06 |