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
  1. 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 is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.