Computation of Geometric Color-Spanning Region for Line Segments

The color-spanning problem for a given set of colored geometric objects finds a region that contains at least one object of each color. Inspired by the application in facility location, we study the color-spanning problem for a given set [Formula: see text] ([Formula: see text]) of colored line segments lying in [Formula: see text], where each line segment is associated with any of [Formula: see text] colors ([Formula: see text]). We compute (i) one color-spanning vertical strip (resp. axis-parallel square) of minimum width (resp. perimeter) in [Formula: see text] (resp. [Formula: see text]) time, (ii) two disjoint color-spanning vertical strips (resp. axis-parallel squares) with minimum width (resp. perimeter) of the larger strip (resp. square) in [Formula: see text] (resp. [Formula: see text]) time. We also compute the [Formula: see text] disjoint color-spanning vertical strips while minimizing the width of the largest strip, in [Formula: see text] time. All such strip problems require a preprocessing of [Formula: see text] time. The same results also exist if [Formula: see text] simple disks or polygons are considered as inputs in the aforementioned problems. We improve the computation time of the minimum perimeter color-spanning square for [Formula: see text] [13] by a [Formula: see text] factor. We design a [Formula: see text]- approximation algorithm to compute a minimum radius color-spanning circle for [Formula: see text] in [Formula: see text] time. Finally, we present an exact algorithm for the restricted version of [Formula: see text] disjoint color-spanning circles problem for [Formula: see text], where the centers of all the circles are constrained to lie on a given line [Formula: see text].