Efficiently Computing the Smallest Axis-Parallel Squares Spanning All Colors

For a set of colored points, a region is called extit{color-spanning} if it contains at least one point of each color. In this paper, we first consider the problem of maintaining extit{the smallest color-spanning interval} for a set of $n$ points with $k$ colors on the real line such that the insertion and deletion of an arbitrary point takes $O(log^2 n)$ worst-case time. Then, we exploit the data structure to show that there is an $O(nlog^2 n)$ time algorithm to compute extit{the smallest color-spanning square} for a set of $n$ points with $k$ colors in the plane. This is a new way to improve the $O(nk log n)$ time algorithm presented by Abellanasetal~citeAbellanas01smallestcolor-spanning} when $k=omega(log n)$. We also consider the problem of computing the smallest color-spanning square in a special case in which we have at most two points from each color. We present an $O(nlog n)$ time algorithm to solve the problem which improves the result presented by Arkinetal~citeArkin} by a factor of $log n$