  In this paper, we study a new type of clustering problem, called {\em
Chromatic Clustering}, in high dimensional space. Chromatic clustering seeks to
partition a set of colored points into groups (or clusters) so that no group
contains points with the same color and a certain objective function is
optimized. In this paper, we consider two variants of the problem, chromatic
$k$-means clustering (denoted as $k$-CMeans) and chromatic $k$-medians
clustering (denoted as $k$-CMedians), and investigate their hardness and
approximation solutions. For $k$-CMeans, we show that the additional coloring
constraint destroys several key properties (such as the locality property) used
in existing $k$-means techniques (for ordinary points), and significantly
complicates the problem. There is no FPTAS for the chromatic clustering
problem, even if $k=2$. To overcome the additional difficulty, we develop a
standalone result, called {\em Simplex Lemma}, which enables us to efficiently
approximate the mean point of an unknown point set through a fixed dimensional
simplex. A nice feature of the simplex is its independence with the
dimensionality of the original space, and thus can be used for problems in very
high dimensional space. With the simplex lemma, together with several random
sampling techniques, we show that a $(1+\epsilon)$-approximation of $k$-CMeans
can be achieved in near linear time through a sphere peeling algorithm. For
$k$-CMedians, we show that a similar sphere peeling algorithm exists for
achieving constant approximation solutions.

Computational Geometry