A separator is a set of curves that separate the plane into the regions with monochromatic objects. Hurtado et al. deal with separability problems for 2-colored objects by a wedge and a strip [5]. Devillers et al. find an algorithm to get minimum cardinality separators for k-colored point sets by parallel lines, rays with common apex and lines through one point for k>2 [8]. In this paper, we generalize some results of [8] to k-colored line segments, polygons and circles with the same time complexity as that of [8]. We also suggest an algorithm to find the minimum cardinality of separators of k-colored points by rays with common apex on a given line and lines through one point on a given line.
Separator는 평면의 object들을 같은 색깔의 object가 같은 connected component 안에 있도록 자르는 곡선들의 set을 의미한다. 두 개의 색이 칠해진 경우에는 많은 연구들이 행해졌고 대부분 분할가능성을 검사하는 알고리즘을 제시하였다. 이논문에서는 Hurtado et al. [8]의 결과를 일반화한 알고리즘을 제시한다. Hurtado et al.의 논문에서는 k개의 색깔로 칠해진 point들에 대한 separator의 최소갯수를 찾는 알고리즘이 제시되었다. 이 논문에서는 위 논문을 일반화해서 k개의 색깔로 칠해진 line segment, polygon, circle들에 대해서 separator의 minimum cardinality를 찾는 알고리즘을 제시하였다.
또한 물체가 점들인 경우에 separator가 한 점을 지나는 ray들이이거나 한 점을 지나는 직선들이고 그 점이 주어진 직선 위에 있을 때 separator의 minimum cardinality를 찾는 알고리즘을 제시하였다. 대부분의 결과들은 주어진 물체들에 대해 dual trasnform을 행한 후 sweeping algorithm을 이용하였다. 따라서 sweeping을 하기 위해 필요한 $O(n^2log n)$ 의 time complexity가 요구된다. 또한 평면 위에 k개의 색으로 칠해진 line segment가 주어졌을 때 k-1개의 평행한 선으로 분할할 수 있는지를 검사하고 또한 분할 가능한 기울기의 interval을 $O(kn)+O(k^2log k)$ 시간에 구하는 알고리즘을 제시하였다. 향후 과제중 하나는 분할자(separator)가 한 점을 지나는 반직선(ray)이고 물체가 line segment인 경우이다. 이 경우에 dual transform을 어떻게 적용할 것인지 연구 중이다. 또한 line segment를 평행한 선으로 분할할 수 있는지 검사할 수 있는 $O(n^2)$ 의 알고리즘도 향후 연구 과제이다. 마지막으로 원을 k-1개의 평행한 선으로 분할할 수 있는 지를 검사하고 분할가능 기울기의 interval을 구하는 것도 연구할 부분이다.
