Dear community,
today, i have a  hopefully interesting  problem of algorithmic optimization.
I have n positions of a cubicle. If you plot all cubicles over another, each cubicle can be seen from outside, maybe just an edge, maybe just some small part of a corner.
Now lets think of a set of cubicle corner and edgepoints and their n transformations. Of course, all of these points (the pointcloud) are (is) covered by the plotted cubicles. (This was the trivial part.)
Now, i want to reduce the number of cubicles, but still nearly (!) want to cover the same space. In other words, i want that the pointcloud of all n cubicles is nearly inside the remaining cubicles.
Now i somehow define a measure for the ratio of covering from one cubicle's points by another cubicles body. By using this measure, i compute a symmetric matrix A where
A(i,j) denotes the ratio, how well the cubicle in position i covers the points of cubicle in position j.
The better the covering, the smaller the value A(i,j). Due to this fact, the entries on the diagonal all equal to zero.
Now i want to prescribe a tolerance tol and want to find the minimal set of cubicles, so that the covering of all n cubicles' points has a ratio of at most tol. To this end, i wrote the following algorithm. (You should mentally identify the rows with the positions of cubicles that should be reduced and the columns with the points of the positions that shall still be nearly covered.)
% for meaningful use of min/max i need a copy of A
B=A; alldistances=distances;
for i=1:n,A(i,i)=1e4;end
% start by keeping all positions
keep=true(1,n);
reduced=1;
while reduced==1,
reduced=0;
I=find(keep);
tmp_A=A(keep,:);tmp_B=B(keep,:);
% find positions that are inside tolerance
nerd=min(tmp_A,[],2);JJ=find(nerd<tol);
for k=1:length(JJ),
J=JJ(k);
% What would happen if deleting position J ?
test=tmp_B([[1:J1],[J+1:end]],:);
if max(min(test,[],1))<tol,
% maximal distance of nearest point sets is still smaller than tolerance
reduced=1;
keep(I(J))=false; % position I(J) can be deleted
break;
end
end
end
index_list=find(keep);
The algorithm works as described above. BUT it needs a lot of time, as the line
test=tmp_B([[1:J1],[J+1:end]],:);
needs a lot of time and may be called often (as it is inside the kloop).
My question to you, humble community, is, if you have some ideas to accelerate the algorithm above.
Thanks in advance,
Johannes Korsawe
