Ackerman, E. and Keszegh, Balázs and Vizer, Máté (2017) Coloring Points with Respect to Squares. DISCRETE AND COMPUTATIONAL GEOMETRY. pp. 128. ISSN 01795376 (In Press)

Text
1512.01953.pdf Download (658kB)  Preview 
Abstract
We consider the problem of 2coloring 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 2colored such that every axisparallel square that contains at least m points from (Formula presented.) contains points of both colors. Our proof is constructive, that is, it provides a polynomialtime algorithm for obtaining such a 2coloring. By affine transformations this result immediately applies also when considering 2coloring points with respect to homothets of a fixed parallelogram.
Item Type:  Article 

Uncontrolled Keywords:  Selfcoverability; Geometric hypergraph coloring; Coverdecomposability 
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 