Rainbow piercing
Rainbow piercing is a problem in computational geometry.
Definitions
There is a set P of n colored points on the real line, and a set J of intervals on the real line.
A subset Q of P is called a rainbow set if it contains at most a single point of each color.
A set of points Q is called a piercing set of J if each interval in J contains at least one point of Q.
The Rainbow piercing problem is the problem of finding a rainbow set Q that is a piercing set for J.
Hardness
The problem is NP-hard.[1] The proof is by reduction from linear SAT.
See also
References
- ↑ Arkin, Esther M.; Banik, Aritra; Carmi, Paz; Citovsky, Gui; Katz, Matthew J.; Mitchell, Joseph S. B.; Simakov, Marina (2018-12-11). "Selecting and covering colored points". Discrete Applied Mathematics. 250: 75–86. doi:10.1016/j.dam.2018.05.011. ISSN 0166-218X.
This article "Rainbow piercing" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Rainbow piercing. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
