Monochromatic Partitioning of Colored Points by Lines
Given a set of n colored points in the plane, we consider the problem of partitioning the underlying space of the points into monochromatic regions using the minimum number of lines. This is a generalized version of the problem of separating non-colored points by lines studied by Har-Peled and Jones in SODA’18. We propose the first approximation algorithm for the problem. Our algorithm returns an O (log n ) factor approximation in O ( mn 2 σ log n ) time, where σ is the number of optimal lines and m is the number of colors