Making triangles colorful
Jean Cardinal, Kolja Knauer, Piotr Micek, Torsten Ueckerdt · Journal of Computational Geometry (Carleton University) · 2013
We prove that for any point set P in the plane, a triangle T, and a positive integer k, there exists a coloring of P with k colors such that any homothetic copy of T containing at least 144k8 points of P contains at least one of each color. This is the first polynomial bound for range spaces induced by homothetic polygons.The only previously known bound for this problem applies to the more general case of octants in ℝ3, but is doubly exponential.