2

I am trying to understand the algorithm of plotting a voronoi diagram. Here is a code I developed using whatever I could get off wikipedia. However the implementation is very slow and the complexity seems $n^2$. Is there a better approach? I am more concerned with the voronoi diagram using the manhattan distance.

close all;
% Voronoi script
p=[100,20;100,190;10,100;170,100;100,100;155,110];
voronoi(p(:,1),p(:,2))
axis([1,200,1,200])
n=zeros (200);
m=n;
d=zeros(size(p));
for i=1:200
    for j=1:200
        % euclidian
        d1=(sum((p-repmat([i,j],size(p,1),1)).^2,2)).^(0.5);   
        % manhattan
        d2=sum(abs(p-repmat([i,j],size(p,1),1)),2);
        idx1=find(d1==min(d1));
        idx2=find(d2==min(d2));
        if length(idx1)>1
            n(i,j)=0;
        else
            n(i,j)=idx1(1);
        end
        if length(idx2)>1
            m(i,j)=0;
        else
            m(i,j)=idx2(1);
        end
    end
end
figure;
axis([1,200,1,200])
%imagesc(flip(n'));
imagesc(n');
hold on;
pf=p;
scatter(pf(:,1),pf(:,2));

figure;
axis([1,200,1,200])
imagesc(m');
hold on;
pf=p;
scatter(pf(:,1),pf(:,2));
Lord Loh.
  • 121
  • isn't $n^2$ polynomial complexity? In de Berg's book on computational geometry an algorithm that takes $n \log n$ time is shown. The algorithm is presented in chapter 7.2. Edit: Sorry I overread the manhatten distance point. Nevertheless, I think it should be modifiable to that case. – Quickbeam2k1 Oct 06 '14 at 06:29
  • Right. $n^2$ is polynomial :p – Lord Loh. Oct 06 '14 at 06:34
  • There is a library called Qhull that does this. I have used it before and it works pretty good (and is fast). – Winther Oct 06 '14 at 06:38
  • @Quickbeam2k1 That an algorithm is polynomial and not exponential does not mean that it is efficient (this distinction is only really useful theoretically). The difference between $n\log n$ and $n^2$ (for large $n$) in real life is the differene between 'easy' and 'fogetaboutit'. – Winther Oct 06 '14 at 18:18
  • @Winther, I don't see your point. What about Quicksort? It sure runs in polynomial time (n^2) but nevertheless it is widely used (I know that the expected time is faster). Originally the op asked for a polynomial time algorithm, but he stated one. But I did not want to talk about that :) Is Qhull applicable to other metrics than the euklidean? – Quickbeam2k1 Oct 06 '14 at 18:34
  • @Quickbeam2k1 Quicksort is $n\log n$. I don't know about other metrics in Qhull, but I doubt it (though it should not be hard to change this). Anyway, my point was to point out that the distnction between 'polynomial' and 'exponential' is not the only important thing about an algorithm. In practice there is a huge difference between e.g. $n$ and $n^2$ etc. The stuff one hears about 'polynomial' vs 'exponential' algorithms as being the great divide is really a theoretical construct. – Winther Oct 06 '14 at 18:41
  • @Winther, you were the first to add the exponential buzzword here and adressed me. I still don't know why :) But maybe we talk at cross-purposes. However, Quicksort is expected to be in $n \log n$ but its worstcase running time is $n^2$ and its not hard to construct a case where this happens (even for the radnom choice of the pivot element) – Quickbeam2k1 Oct 06 '14 at 20:24
  • @Quickbeam2k1 Ahh.. I did not see that OP had written 'polynomial complexity' in this first post and then choose to remove it. I though you were saying '$n^2$ is polynomial so it should be good'. The reason I commented is that I see that misconception so often among mathematicians - and the coder in me felt the need to speak out:) Sorry about that! – Winther Oct 06 '14 at 21:41

0 Answers0