function initT = cfp_init_regular(Pts, b, ColorPartition)
%
% A greedy algorithm to find a colorful set of points from given colorful
% points.
%
% **********
% * Syntax *
% **********
% initT = cfp_init_regular(Pts, ColorPartition , b)
%
% *******************
% * Input Arguments *
% *******************
% Pts is a matrix storing the coordinates of points. Each column of Pts
% stores the coordinate of one point. The number of rows is d, which is
% the number of dimensions of the Euclidean space. The points in each color
% of Pts must contain b in their convex hull.
%   b is a column vector representing a point in the d-Euclidean space.
%   ColorPartition is a row vector of length (d+1). Each element is an
% integer not less than (d+1), specifying the number of points in a color.
% For example [3 4 3] tells that the first 3 points in Pts are in the first
% color, the following 4 points are in the second color, and so on.
% 
% ********************
% * Output Arguments *
% ********************
% initT is a row vector of length (d+1). Its elements are column indices of
% Pts, specifying a colorful set of points (one point for each color).
%
% *************
% * Algorithm *
% *************
% The angle between two vertices of the regular simplex centered at origin
% is calculated. Points of each color are selected to make the angle with 
% the other points as close to the ideal angle as possible.
%
%


%%%%%%%%%%%%%%%%%%%%%%%%% Internal Comments %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Written by Sui Huang, Advanced Optimization Lab, McMaster University,
% Hamilton, Ontario, Canada.
% 
% ************************
% * Modification History *
% ************************
% May  2005: First version.
% July 2005: Added comments.
% July 2007: Unified interface in the package for the thesis
%            "Colourful Feasibility Problem: Algorithm, Bounds and
%            Implications".
% 


d = length(b);
ideal_dot = -1/d;

% Get the number of colors.
l = length(ColorPartition);

% Allocate memory for initT.
initT = zeros(1, l);

% Choose the first point for the first color.
initT(1) = 1;
% Initialize the projection point.
p = Pts(:,1);
% base helps to enumerate all the point indices of each colors.
base = ColorPartition(1);
% Choose one point from each of the rest colors.
for i = 2:l
    % Get the maximum of the minimum distance and the corresponding point.
    min_max_dotdiff = 2;
    for j = (base+1):(base+ColorPartition(i))
        % Get the minimum distance to the points already in colorful set.
        max_dotdiff = 0;
        for k = 1:(i-1)
            dotdiff = abs( sum(Pts(:,j).*Pts(:,initT(k))) - ideal_dot );
            if (dotdiff > max_dotdiff)  max_dotdiff = dotdiff;  end
        end
        % Keep the best point by comparison.
        if (max_dotdiff < min_max_dotdiff)
            min_max_dotdiff = max_dotdiff;
            pt_index = j;
        end
    end
    % Insert the selected point into the set represented by initT.
    initT(i) = pt_index;
    % Prepare base for next color.
    base = base + ColorPartition(i);
end

return