Algorithms for Dividing 1-dimensional Point Set into Rainbow Subsets

Sang Duk Yoon

http://doi.org/10.5626/JOK.2022.49.3.201

When color is assigned to data that are expressed by a set of points in geometric space, a set of points that includes at least one point of each color is defined as a color-spanning set or a rainbow set. This paper suggests algorithms for determining optimal ways of selecting points from a colored one-dimensional point set such that the subsets composed of contiguous (selected) points and the set of remaining points are all rainbow sets. The suggested algorithms aim to minimize the number of selected points or minimize the total lengths of the regions that contain the selected points.