Smallest Color-Spanning Strip

We are given a set of nn point sites in the plane and knk\leq n colors, each site is associated one color. A region of the plane is called color-spanning if it contains at least one point of each color. We wish to compute the two parallel lines in the plane that contain all colors in between them such that their distance is minimized.

Parameters

  • nn: number of points
  • kk: number of colors

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 1 of 1 reductions

Other relevant algorithms

Insuffient Data to display table