Complexity And Approximation Algorithm Of Partitioning Colored Point Set Into Monochromatic Parts With Straight Line

Partitioning colored point set into monochromatic parts is an optimization problem in computational geometry, it focuses on how to dissect the plan with polychrome points into regions with monochrome points. But the approach of partitioning with polygon can’t get good partition results now, this paper came up with an approach of partitioning with straight line, we discretized this prob-lem to prove that non-deterministic Turing Machine can decide this problem. We reduced Max2SAT problem to this problem in polynomial time, and proved that it’s NP-hard. Then partitioning colored point set into monochromatic parts with straight line problem is in NP-complete class. Finally, we gave an approxima-tion algorithm. By using L-reduction from SETCOVER problem, we proved the approximation ratio is O(lgn).