2012/12/11 by Jean Cardinal, Cardinal, Jean, Kolja Knauer +5 · 1 citation
Engineering · #Architecture and Computational Design #Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1212.2346
openalex publication_date 2012/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ck8 points of P, for some constant c, 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 R3, but is doubly exponential.