Thread Subject: finding minimum distance in a set of points

Is there a good way in Matlab to find the minimum
point-point distance in a set of points? I've come up with a
few methods, and the best I've figured out so far is this:

N=10; % probably will want bigger N

% generate N points in 2D
p=rand(N,2);

% generate N*(N-1)/2 x 2 array of pair indices
[x y]=meshgrid(1:N);
i=find(triu(ones(N)-eye(N)));
i=[x(i) y(i)];

% compute all pairwise distances
d2=(p(i(:,1),1)-p(i(:,2),1)).^2 + ...
   (p(i(:,1),2)-p(i(:,2),2)).^2;

% find minimum distance and corresponding points
[d2min imin]=min(d2);
dmin=sqrt(d2min)
p1 = p(i(imin,1),:)
p2 = p(i(imin,2),:)

This seems to work pretty well, it beats for loops for N>20
or so on my computer, but it seems like there should be a
better way. Also, I don't see a straightforward way to
extend this to higher dimensions, which I would like to do.

I basically wrote for loops to do it, and then tried to come
up with an array of the indices that the for loops would
generate, in order to vectorize the operation. This is easy
for 2D, using triu, but is there some way to generate a
similar set of index pairs in higher dimensions? Or what if
I wanted to generate index triplets? Or index M-tuplets in D
dimensions? Are there any built-in functions that do this
kind of thing?

Thanks

"Alan B" <monguin61@yahoo.com> wrote in message
<g6v8fd$ntc$1@fred.mathworks.com>...
> Is there a good way in Matlab to find the minimum
> point-point distance in a set of points? I've come up with a
> few methods, and the best I've figured out so far is this:
>
> N=10; % probably will want bigger N
>
> % generate N points in 2D
> p=rand(N,2);
>
> % generate N*(N-1)/2 x 2 array of pair indices
> [x y]=meshgrid(1:N);
> i=find(triu(ones(N)-eye(N)));
> i=[x(i) y(i)];
>
> % compute all pairwise distances
> d2=(p(i(:,1),1)-p(i(:,2),1)).^2 + ...
> (p(i(:,1),2)-p(i(:,2),2)).^2;
>
> % find minimum distance and corresponding points
> [d2min imin]=min(d2);
> dmin=sqrt(d2min)
> p1 = p(i(imin,1),:)
> p2 = p(i(imin,2),:)
>
> This seems to work pretty well, it beats for loops for N>20
> or so on my computer, but it seems like there should be a
> better way. Also, I don't see a straightforward way to
> extend this to higher dimensions, which I would like to do.
>
> I basically wrote for loops to do it, and then tried to come
> up with an array of the indices that the for loops would
> generate, in order to vectorize the operation. This is easy
> for 2D, using triu, but is there some way to generate a
> similar set of index pairs in higher dimensions? Or what if
> I wanted to generate index triplets? Or index M-tuplets in D
> dimensions? Are there any built-in functions that do this
> kind of thing?

Don't do that, use delaunay and delaunayn:

N=10000; % is it big enough?

% generate N points in 2D
p=rand(N,2);

tic
% generate N*(N-1)/2 x 2 array of pair indices
[x y]=meshgrid(1:N);
i=find(triu(ones(N)-eye(N)));
i=[x(i) y(i)];

% compute all pairwise distances
d2=(p(i(:,1),1)-p(i(:,2),1)).^2 + ...
   (p(i(:,1),2)-p(i(:,2),2)).^2;

% find minimum distance and corresponding points
[d2min imin]=min(d2);
dmin=sqrt(d2min) % 13.596138 seconds.
toc

% Delaunay way:

tic
tri=delaunay(p(:,1),p(:,2));
d2fun = @(k,l) sum((p(k,:)-p(l,:)).^2,2);
d2tri = @(k) [d2fun(tri(k,1),tri(k,2)) ...
              d2fun(tri(k,2),tri(k,3)) ...
              d2fun(tri(k,3),tri(k,1))];
dtri=cell2mat(arrayfun(@(k) d2tri(k),...
              (1:size(tri,1))','UniformOutput',0));
d=sqrt(min(dtri(:))) % 1.002932 seconds
toc

The effect may be even greater for higher dimensions.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in
message <g6va22$1vg$1@fred.mathworks.com>...
> "Alan B" <monguin61@yahoo.com> wrote in message
> <g6v8fd$ntc$1@fred.mathworks.com>...
> > Is there a good way in Matlab to find the minimum
> > point-point distance in a set of points? I've come up with a
> > few methods, and the best I've figured out so far is this:
> >
> > N=10; % probably will want bigger N
> >
> > % generate N points in 2D
> > p=rand(N,2);
> >
> > % generate N*(N-1)/2 x 2 array of pair indices
> > [x y]=meshgrid(1:N);
> > i=find(triu(ones(N)-eye(N)));
> > i=[x(i) y(i)];
> >
> > % compute all pairwise distances
> > d2=(p(i(:,1),1)-p(i(:,2),1)).^2 + ...
> > (p(i(:,1),2)-p(i(:,2),2)).^2;
> >
> > % find minimum distance and corresponding points
> > [d2min imin]=min(d2);
> > dmin=sqrt(d2min)
> > p1 = p(i(imin,1),:)
> > p2 = p(i(imin,2),:)
> >
> > This seems to work pretty well, it beats for loops for N>20
> > or so on my computer, but it seems like there should be a
> > better way. Also, I don't see a straightforward way to
> > extend this to higher dimensions, which I would like to do.
> >
> > I basically wrote for loops to do it, and then tried to come
> > up with an array of the indices that the for loops would
> > generate, in order to vectorize the operation. This is easy
> > for 2D, using triu, but is there some way to generate a
> > similar set of index pairs in higher dimensions? Or what if
> > I wanted to generate index triplets? Or index M-tuplets in D
> > dimensions? Are there any built-in functions that do this
> > kind of thing?
>
> Don't do that, use delaunay and delaunayn:
>
> N=10000; % is it big enough?
>
> % generate N points in 2D
> p=rand(N,2);
>
> tic
> % generate N*(N-1)/2 x 2 array of pair indices
> [x y]=meshgrid(1:N);
> i=find(triu(ones(N)-eye(N)));
> i=[x(i) y(i)];
>
> % compute all pairwise distances
> d2=(p(i(:,1),1)-p(i(:,2),1)).^2 + ...
> (p(i(:,1),2)-p(i(:,2),2)).^2;
>
> % find minimum distance and corresponding points
> [d2min imin]=min(d2);
> dmin=sqrt(d2min) % 13.596138 seconds.
> toc
>
> % Delaunay way:
>
> tic
> tri=delaunay(p(:,1),p(:,2));
> d2fun = @(k,l) sum((p(k,:)-p(l,:)).^2,2);
> d2tri = @(k) [d2fun(tri(k,1),tri(k,2)) ...
> d2fun(tri(k,2),tri(k,3)) ...
> d2fun(tri(k,3),tri(k,1))];
> dtri=cell2mat(arrayfun(@(k) d2tri(k),...
> (1:size(tri,1))','UniformOutput',0));
> d=sqrt(min(dtri(:))) % 1.002932 seconds
> toc
>
> The effect may be even greater for higher dimensions.
>
> Bruno
>
>
>

Thanks, Bruno. Actually, the first method seems to be faster
than the delaunay method for me, for N<1000, which is big
enough for me. I guess your method uses less memory though,
and it looks like I can extend it to 3D, with delaunay3,
which is basically what I want.

"Alan B" <monguin61@yahoo.com> wrote in message
<g6vaqe$ig5$1@fred.mathworks.com>...

>
> Thanks, Bruno. Actually, the first method seems to be faster
> than the delaunay method for me, for N<1000, which is big
> enough for me.

Alan, not yet my last word!!!

N=1000;

% generate N points in 2D
p=rand(N,2);

tic
% generate N*(N-1)/2 x 2 array of pair indices
[x y]=meshgrid(1:N);
i=find(triu(ones(N)-eye(N)));
i=[x(i) y(i)];

% compute all pairwise distances
d2=(p(i(:,1),1)-p(i(:,2),1)).^2 + ...
   (p(i(:,1),2)-p(i(:,2),2)).^2;

% find minimum distance and corresponding points
[d2min imin]=min(d2);
dmin=sqrt(d2min) % 0.289896 seconds
toc

% Delaunay way with array, even faster:
tic
tri=delaunay(p(:,1),p(:,2));
tri=tri(:,[1:end 1]);
dx = diff(reshape(p(tri,1),size(tri)),1,2);
dy = diff(reshape(p(tri,2),size(tri)),1,2);
dmin = sqrt(min(dx(:).^2+dy(:).^2)) % 0.093659 seconds
toc

% Bruno

On 1 Aug, 17:01, "Alan B" <mongui...@yahoo.com> wrote:
> Is there a good way in Matlab to find the minimum
> point-point distance in a set of points? I've come up with a
> few methods, and the best I've figured out so far is this:
...
> This seems to work pretty well, it beats for loops for N>20
> or so on my computer,

No, it doesn't. There are for-loops hidden inside the 'find'
and 'min' functions you use. You only see the diffrence between
two implementations of for loops.

> but it seems like there should be a
> better way. Also, I don't see a straightforward way to
> extend this to higher dimensions, which I would like to do.

This is a standard exercise in geometry. Check out the
1993 book by Preparata and Shamos to find an efficient
recipe.

> I basically wrote for loops to do it, and then tried to come
> up with an array of the indices that the for loops would
> generate, in order to vectorize the operation.

Forget about that. This is nothing more than a direct search
which requires O(N^2) time. The job can be done in O(NlogN)
time, but you need to use a completely different strategy.

Rune

Rune Allnor <allnor@tele.ntnu.no> wrote in message
<bc2dfbf2-bf15-49ed-aac3-dab1d24e6c3b@34g2000hsh.googlegroups.com>...
> On 1 Aug, 17:01, "Alan B" <mongui...@yahoo.com> wrote:
> > Is there a good way in Matlab to find the minimum
> > point-point distance in a set of points? I've come up with a
> > few methods, and the best I've figured out so far is this:
> ...
> > This seems to work pretty well, it beats for loops for N>20
> > or so on my computer,
>
> No, it doesn't. There are for-loops hidden inside the 'find'
> and 'min' functions you use. You only see the diffrence
between
> two implementations of for loops.
>
> > but it seems like there should be a
> > better way. Also, I don't see a straightforward way to
> > extend this to higher dimensions, which I would like to do.
>
> This is a standard exercise in geometry. Check out the
> 1993 book by Preparata and Shamos to find an efficient
> recipe.
>
> > I basically wrote for loops to do it, and then tried to come
> > up with an array of the indices that the for loops would
> > generate, in order to vectorize the operation.
>
> Forget about that. This is nothing more than a direct search
> which requires O(N^2) time. The job can be done in O(NlogN)
> time, but you need to use a completely different strategy.

The complexity of (well implemented) Delaunay algorithm in a
worse case is O(N^ceil(d/2)) and for well distributed point
set (more or less uniform) is O(N). N is number of points
and d is the dimension. So:

In 2D, Delaunay complexity is O(N) is any case.

In 3D, Delaunay complexity is O(N^2) in the worse case and
O(N) in average. Quite good no?

The post-search for min distance part is of course at
(d+1)*O(N) in complexity.

Bruno

On 2 Aug, 12:28, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:

> In 2D, Delaunay complexity is O(N) is any case.

Could you prove that, please?

Rune

Rune Allnor <allnor@tele.ntnu.no> wrote in message
<5449ab65-b826-44bd-a160-c20959eccbb1@i76g2000hsf.googlegroups.com>...
> On 2 Aug, 12:28, "Bruno Luong"
<b.lu...@fogale.findmycountry> wrote:
>
> > In 2D, Delaunay complexity is O(N) is any case.
>
> Could you prove that, please?
>

Not me, but here is the reference paper:

P. McMullen. The maximum number of faces of a convex
polytope. Mathematika, 17:179–184, 1970.

Bruno

On 2 Aug, 13:25, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:
> Rune Allnor <all...@tele.ntnu.no> wrote in message
>
> <5449ab65-b826-44bd-a160-c20959ecc...@i76g2000hsf.googlegroups.com>...
>
> > On 2 Aug, 12:28, "Bruno Luong"
> <b.lu...@fogale.findmycountry> wrote:
>
> > > In 2D, Delaunay complexity is O(N) is any case.
>
> > Could you prove that, please?
>
> Not me, but here is the reference paper:
>
> P. McMullen. The maximum number of faces of a convex
> polytope. Mathematika, 17:179–184, 1970.

Have you actually read the paper or do you merely refer
to what you think it says?

Rune

Rune Allnor <allnor@tele.ntnu.no> wrote in message
<e3533450-2671-4b94-839c-ce0d3c7b04de@m3g2000hsc.googlegroups.com>...

>
> Have you actually read the paper or do you merely refer
> to what you think it says?
>

No I haven't read it. But this result well known and I knew
it since I was lectured at university on the topic (I was
not in a geometry/computation department which is but 1/4 of
staffs of our math department is on this topic, I very good
friend of mine who works on this subject, actually on the
perturbation of triangulation by errors). If are interested
and wish to contact people on this topic for further detail,
just let me know.

Here is an experiment test with MATLAB on my PC, it shows a
quite good linearity:

N=10, time=0.147329
N=100, time=0.058632
N=1000, time=0.080535
N=10000, time=0.852366
N=100000, time=8.593533
N=1000000, time=89.974866

% Code
clear all
N=10.^(1:6); % 10 to a billion
time=zeros(size(N));
for k=1:length(N)
    % generate N points in 2D
    p=rand(N(k),2);
    
    % Delaunay way with array, even faster:
    tstart=tic;
    tri=delaunay(p(:,1),p(:,2));
    tri=tri(:,[1:end 1]);
    dP = diff(reshape(p(tri,:),[size(tri) size(p,2)]),1,2);
    d2 = sum(dP.^2,3);
    dmin = sqrt(min(d2(:)));
    time(k)=toc(tstart);
    fprintf('N=%d, time=%f\n', N(k), time(k));
end
% Plot time vs number of data point
loglog(N,time,'-o')
xlabel('Number of data')
ylabel('Time [s]')
grid on

% Bruno

On 2 Aug, 15:09, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:
> Rune Allnor <all...@tele.ntnu.no> wrote in message
>
> <e3533450-2671-4b94-839c-ce0d3c7b0...@m3g2000hsc.googlegroups.com>...
>
>
>
> > Have you actually read the paper or do you merely refer
> > to what you think it says?
>
> No I haven't read it. But this result well known and I knew
> it since I was lectured at university on the topic

"Was lectured on the topic" - you *took* a class? Not *taught*
a class?

> (I was
> not in a geometry/computation department which is but 1/4 of
> staffs of our math department is on this topic, I very good
> friend of mine who works on this subject, actually on the
> perturbation of triangulation by errors).

So you don't know the *subject* but you know *people* who
know the subject?

> If are interested
> and wish to contact people on this topic for further detail,
> just let me know.

Thanks for the offer, but I know the topic well enough. The
insertion of *one* point in a Delaunay triangulation which
already contains N points takes O(N) time. Since you have N
points to insert the worst-case scenario is that it takes O(N^2)
time to build a triangulation from scratch.

There are several strategies to try and beat that situation.
One is to randomize the order the points are inserted, and
make a search tree along the way, meaning it tales O(logN)
time to find the location of the new point, requiring an
*expected* O(NlogN)time to insert N points. No guarantees,
though, as one very well might end up with an O(N) search
for locations. It doesn;t happen very often, but there is
some residual non-zero probability that it might happen.

Another method is to sort the points first in O(NlogN) time,
and then insert the points. While this method on average is
fast, there are no guarantees that you can avoid the worst
case scenario where one ends up with O(N^2) triangulation time.

> Here is an experiment test with MATLAB on my PC, it shows a
> quite good linearity:

It doesn't prove anything. If you check out deBerg & al's
book on computational geometry (I am sure your colleagues
have it) you will find an example of a pathologic set of
points which will exhibit the worst-case behaviour.

Rune

Rune Allnor <allnor@tele.ntnu.no> wrote in message
<8b35bb69-3422-4ee2-9ded-
>
> So you don't know the *subject* but you know *people* who
> know the subject?

"knowing" is a not black and white thing IMHO, but yes
geometry computation is not my major expertise and I don't
deal with it daily - if that information is an important
criteria for you Rune in the discussion.

Bruno

On 2 Aug, 18:21, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:
> Rune Allnor <all...@tele.ntnu.no> wrote in message
>
> <8b35bb69-3422-4ee2-9ded-
>
>
>
> > So you don't know the *subject* but you know *people* who
> > know the subject?
>
> "knowing" is a not black and white thing IMHO, but yes
> geometry computation is not my major expertise and I don't
> deal with it daily - if that information is an important
> criteria for you Rune in the discussion.

It's not important to me in any other way than that it
explains why you come up with positively wrong information.
Knowing what you don't know is at least as important as
knowing what you do know. (Yes. That actually makes sense.)

Rune

Rune Allnor <allnor@tele.ntnu.no> wrote in message
<e6b3bb92-4a70-4e6c-87b5-80c32a2068a7@j22g2000hsf.googlegroups.com>...
> On 2 Aug, 18:21, "Bruno Luong"
<b.lu...@fogale.findmycountry> wrote:
> > Rune Allnor <all...@tele.ntnu.no> wrote in message
> >
> > <8b35bb69-3422-4ee2-9ded-
> >
> >
> >
> > > So you don't know the *subject* but you know *people* who
> > > know the subject?
> >
> > "knowing" is a not black and white thing IMHO, but yes
> > geometry computation is not my major expertise and I don't
> > deal with it daily - if that information is an important
> > criteria for you Rune in the discussion.
>
> It's not important to me in any other way than that it
> explains why you come up with positively wrong information.
> Knowing what you don't know is at least as important as
> knowing what you do know. (Yes. That actually makes sense.)
>

I see it's important for you despite you make the claim of
the contrary. May be I'm wrong about O(N), at least I show a
scientific paper with a results using may be a non valid
assumption that escapes me. Fine.

However what I expect from someone who really knows the
topic is pointing to me what is the assumption used by the
paper that is not true, thus why the claimed complexity is
not right. I have not read any of this in your post. You
were merely giving examples two or three algorithms that do
not have complexities go under O(N)log(N). This - of course
you must be aware - does not disprove the claim of the paper.

You wanted to prove you are the one who are working on the
topic and I'm not, so my claim is false is your is right.
You have not showed us why my claim is wrong beside telling
it. That's what you were doing, and to be honest with you, I
do not like this attitude at all.

Bruno

PS: And yes I have programmed myself the Voronoi/Delaunay
stuff at O(N)*log(N). I was involved in one of the proof of
one the the theorem in the PhD thesis of my friend. Just to
tell you so that you also know what I know.

On 2 Aug, 21:02, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:
> Rune Allnor <all...@tele.ntnu.no> wrote in message
>
> <e6b3bb92-4a70-4e6c-87b5-80c32a206...@j22g2000hsf.googlegroups.com>...
>
>
>
>
>
> > On 2 Aug, 18:21, "Bruno Luong"
> <b.lu...@fogale.findmycountry> wrote:
> > > Rune Allnor <all...@tele.ntnu.no> wrote in message
>
> > > <8b35bb69-3422-4ee2-9ded-
>
> > > > So you don't know the *subject* but you know *people* who
> > > > know the subject?
>
> > > "knowing" is a not black and white thing IMHO, but yes
> > > geometry computation is not my major expertise and I don't
> > > deal with it daily - if that information is an important
> > > criteria for you Rune in the discussion.
>
> > It's not important to me in any other way than that it
> > explains why you come up with positively wrong information.
> > Knowing what you don't know is at least as important as
> > knowing what you do know. (Yes. That actually makes sense.)
>
> I see it's important for you despite you make the claim of
> the contrary. May be I'm wrong about O(N), at least I show a
> scientific paper with a results using may be a non valid
> assumption that escapes me. Fine.

Either that paper discusses something completeky different
than you think it does, or the claim put forward in that
aper is positively wrong.

> However what I expect from someone who really knows the
> topic is pointing to me what is the assumption used by the
> paper that is not true, thus why the claimed complexity is
> not right.

Nope. What you would expect is to read the paper yourelf
before you start talking about it as if you have.

> I have not read any of this in your post. You
> were merely giving examples two or three algorithms that do
> not have complexities go under O(N)log(N). This - of course
> you must be aware - does not disprove the claim of the paper.

I did point you to the obvious fact that a pathological
textbook example exists, which demonstrates that inserting
*one* point into a Delaunay tesselation which already
contains N points, is O(N) complexity.

> You wanted to prove you are the one who are working on the
> topic and I'm not, so my claim is false is your is right.
> You have not showed us why my claim is wrong beside telling
> it. That's what you were doing, and to be honest with you, I
> do not like this attitude at all.

That's too bad. I'm used to dealing with people who are able
and willing to read the basic literature before they make
bold statements. If that's an attitude which is problematic
to you, you might want to discuss your education and
preparation for real-life work with the Dean of whatever
university you went to, not with me.

As for the textbook example, it is utterly trivial and
is demonstrated by the matlab script below.

Define a sequence of points Pn = {p1,...,pn} where

pn = (a^(n-1),a^(2(n-1)))

where a is some real scalar 0 < a < 1. The sequence starts
at (1,1) and traces the parabola y=x^2 asymptotically
towards (0,0).

Define Dn as the n-point Delaunay tesselation of the set Pn.

Start with some tesselation Dn, n>2, add the next point pn+1
and compute the new tesselation Dn+1.

The key is to realize that none of the internal edges internal
to Dn (edges not on the convex hull of Dn) remain in the new
tesselation Dn+1. This means that with each point pn+1 added
to the tesselation, one needs to update *all* the n-3 or so
internal edges which already existed in the tesselation Dn.

This is O(N^2) behaviour as clear as it comes.

In the script below you can see this very clearly, as the
previous tesselation Dn-1 is plotted in red under Dn which
is plotted in blue.

Rune

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
PlotRows = 3;
PlotCols = 3;
NPlots = PlotCols*PlotRows;

a=0.7;

P=reshape(0:NPlots+1,NPlots+2,1)*[1,2];
P = a.^P;

clf
for n=1:NPlots
   pp=P(1:n+2,:);
   Dn=delaunay(pp(:,1),pp(:,2));
   subplot(PlotCols,PlotRows,n)
   dn=trimesh(Dn,pp(:,1),pp(:,2));
   hold on
   for m=1:length(dn)
       set(dn(m),'color','b');
   end
   plot(pp(:,1),pp(:,2),'.b')
   axis([-0.05,1.05,-0.05,1.05])
   set(gca,'xtick',[],'ytick',[])
   ts=['D_{',num2str(n+2),'}'];
   title(ts,'interpreter','tex')

   if n<NPlots
     subplot(PlotCols,PlotRows,n+1)
     dn=trimesh(Dn,pp(:,1),pp(:,2));
     hold on
     for m=1:length(dn)
       set(dn(m),'color','r');
     end
   end
end

Rune Allnor <allnor@tele.ntnu.no> wrote in message
<6d4ad16f-e455-4759-9b03-1a5eb385cf30@d45g2000hsc.googlegroups.com>...

>
> Nope. What you would expect is to read the paper yourelf
> before you start talking about it as if you have.

True, that would be indeed ideal, but I do not have time nor
enough expertise to read through all the papers I come
across and fully understand it. I do know that Fermat's
theorem have been proven, but I'm unable to read Wiles's
paper, and I will not hesitate to apply it in real life if
opportunity arises.

>
> That's too bad. I'm used to dealing with people who are able
> and willing to read the basic literature before they make
> bold statements. If that's an attitude which is problematic
> to you, you might want to discuss your education and
> preparation for real-life work with the Dean of whatever
> university you went to, not with me.

Read from these respective papers:

http://www.lis.inpg.fr/pages_perso/attali/Publications/lbcdtpps-sm02.ps

"It is well known that the complexity of Delaunay
triangulation of n point in R^d, i.e., the number of its
simplices can be O(ceil(d/2)) [Boissonnat, Yvinec,
Algorithmic Geometry, Cambridge Univ Press, UK, 1998]

http://cis.poly.edu/~aronov/papers/voronoi-lb.ps

In R^d, the problem has been explored with less success. The
worst-case complexity of Euclidean Voronoi diagram of points
is O(ceil(d/2)) and the same bounds have been proven for
Linfinity metric [Boissonnat, Shahir, Tagansky, Yvinec,
1998] [Edelsbrunner, 1987].

http://www.ii.uni.wroc.pl/~mbi/papers/2005-04-ewcg/average-voronoi-presentation.pdf

Worst case complexity O(ceil(d/2)) [Klee, 1980, Seidel 1987].

And FYI, I'm dealing with problem is real life since 10
years (However I cannot pretend I never make a mistake, but
I rarely make the same miskake twice). And if you wonder
where I'm graduate: The same university than Boissonnat who
has been cited above.

>
> As for the textbook example, it is utterly trivial and
> is demonstrated by the matlab script below...

Thanks for the example, I appreciate it.

But may be I miss something: what you have shown is that the
lower bound complexity of an *INCREMENTAL* delaunay
tessalation is at best O(N*logN). Where does it shows that
*ALL* algorithms cannot beat it?

Just to make a metaphore: to show a sorting algorithm cannot
beat O(N*log(N)), one cannot take a quick sort algorithm as
case of study: Otherwise it would show a behavior of O(N^2)
in the worst case for sorting!

But dont' get me wrong: this does not mean that I reject
your conclusion of O(N.log(N)) for Delaunay in R^2. I'm
still not convinced yet from what has been shown.

So I'm modestly still persuaded by my previous bold
statement on the possible Delaunay complexity of O(N) on R^2.

Bruno

On 3 Aug, 14:04, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:
> Rune Allnor <all...@tele.ntnu.no> wrote in message
>
> <6d4ad16f-e455-4759-9b03-1a5eb385c...@d45g2000hsc.googlegroups.com>...
>
>
>
> > Nope. What you would expect is to read the paper yourelf
> > before you start talking about it as if you have.
>
> True, that would be indeed ideal, but I do not have time nor
> enough expertise to read through all the papers I come
> across and fully understand it. I do know that Fermat's
> theorem have been proven, but I'm unable to read Wiles's
> paper,

So am I. which is one important reason why I don't
comment on Wiles' proof.

> and I will not hesitate to apply it in real life if
> opportunity arises.

Maybe you would. I would be very hesitant to use a theorem
I do not understand; the least I would do is to include enough
CYA phrases to make anybody reading my comments that this
is taken at face value, not because of any deeper
understanding.

> > That's too bad. I'm used to dealing with people who are able
> > and willing to read the basic literature before they make
> > bold statements. If that's an attitude which is problematic
> > to you, you might want to discuss your education and
> > preparation for real-life work with the Dean of whatever
> > university you went to, not with me.
>
> Read from these respective papers:
...
> In R^d, the problem has been explored with less success. The
> worst-case complexity of Euclidean Voronoi diagram of points
> is O(ceil(d/2))
...

What is d here? The number of dimensions? The number of points?
If the former, what's the relevance to this discussion?

> And FYI, I'm dealing with problem is real life since 10
> years (However I cannot pretend I never make a mistake, but
> I rarely make the same miskake twice). And if you wonder
> where I'm graduate: The same university than Boissonnat who
> has been cited above.

That doesn't help much if you didn't learn from him.

> > As for the textbook example, it is utterly trivial and
> > is demonstrated by the matlab script below...
>
> Thanks for the example, I appreciate it.
>
> But may be I miss something: what you have shown is that the
> lower bound complexity of an *INCREMENTAL* delaunay
> tessalation is at best O(N*logN).

No, I have not. I have shown that the *worst*case* is O(N^2).
I have commented that various strategies exist to try and
avoid the worst cases, although no guarantees can be given for
any strategy.

> Where does it shows that
> *ALL* algorithms cannot beat it?
>
> Just to make a metaphore: to show a sorting algorithm cannot
> beat O(N*log(N)), one cannot take a quick sort algorithm as
> case of study: Otherwise it would show a behavior of O(N^2)
> in the worst case for sorting!

If you can find an algorithm which is guaranteed to work faster
than O(N^2) with the example I showed, I am sure Boissonnant
will be proud to be a co-author on the paper where you publish it.

> But dont' get me wrong: this does not mean that I reject
> your conclusion of O(N.log(N)) for Delaunay in R^2. I'm
> still not convinced yet from what has been shown.

Again, I haven't shown anything regarding O(NlogN); I have
demonstrated O(N^2) as worst-case behaviour.

> So I'm modestly still persuaded by my previous bold
> statement on the possible Delaunay complexity of O(N) on R^2.

If such an algorithm existed, I can assure you Boissonnant
would have described it in his text on geometric computations.
He did not mention anything of the sort.

Rune

Rune Allnor <allnor@tele.ntnu.no> wrote in message
<adfdeb3b-76f5-4ef4-b059-9db51e7ba6e3@a1g2000hsb.googlegroups.com>...

>
> What is d here? The number of dimensions? The number of
points?
> If the former, what's the relevance to this discussion?

d is the number of dimension, d=2 for delaunay in the
*plane*. The formula tells that the worst case complexity is

O(N) for R^2
O(N^2) for R^3
O(N^2) for R^4
O(N^3) for R^5, etc...
 
>
> > And FYI, I'm dealing with problem is real life since 10
> > years (However I cannot pretend I never make a mistake, but
> > I rarely make the same miskake twice). And if you wonder
> > where I'm graduate: The same university than Boissonnat who
> > has been cited above.
>
> That doesn't help much if you didn't learn from him.

You again insists on what I know and what I don't. I already
told enough detail about what I know and what I don't. Do
you want the name of the professor that teached me Geometry
algorithmic? My notes of his lecture? What practical
examples have we programmed on the computer? My grades?

>
> If you can find an algorithm which is guaranteed to work
faster
> than O(N^2) with the example I showed, I am sure Boissonnant
> will be proud to be a co-author on the paper where you
publish it.

Let me put it clear: I don't know Boissonnat personally, but
few other people who work with him. I don't know the topic
well enough to defend it, but that what I have been taught
and believe on. I proposed you to contact these people if
you have any concern about the result and if you are
interested to figure out what behind it.

>
> If such an algorithm existed, I can assure you Boissonnant
> would have described it in his text on geometric computations.
> He did not mention anything of the sort.
>

Hey, you could of course go on and make your logic in that
sort: "such result must be wrong because Mr X did not
publish Y"; "Mr B does not *know* topic Z so his claim about
C must be false", etc... That's up to up Rune. I would not
venture to tell you whereas it will be good or bad in the
real life, I just don't share with you that kind of logic.

Bruno


  

On 3 Aug, 15:02, "Bruno Luong" <b.lu...@fogale.findmycountry> wrote:
> Rune Allnor <all...@tele.ntnu.no> wrote in message
>
> <adfdeb3b-76f5-4ef4-b059-9db51e7ba...@a1g2000hsb.googlegroups.com>...
>
>
>
>
>
> > What is d here? The number of dimensions? The number of
> points?
> > If the former, what's the relevance to this discussion?
>
> d is the number of dimension, d=2 for delaunay in the
> *plane*. The formula tells that the worst case complexity is
>
> O(N) for R^2
> O(N^2) for R^3
> O(N^2) for R^4
> O(N^3) for R^5, etc...

As the example I posted earlier shows, there is at least one case
in 2D which shows O(N^2) complexity. So the claim that these
formulas are worst case is clearly wrong.

It's been a while since I read Boissonnant's book so I would have
to check it again, but my guess is that these formulas are
Omega(N^q),
i.e. that they mean that any algorithm in R^2 is *at*least* O(N)
complexity; any algorithm in R^3 is *at*least* O(N^2) complexity, etc.

> > > And FYI, I'm dealing with problem is real life since 10
> > > years (However I cannot pretend I never make a mistake, but
> > > I rarely make the same miskake twice). And if you wonder
> > > where I'm graduate: The same university than Boissonnat who
> > > has been cited above.
>
> > That doesn't help much if you didn't learn from him.
>
> You again insists on what I know and what I don't. I already
> told enough detail about what I know and what I don't. Do
> you want the name of the professor that teached me Geometry
> algorithmic? My notes of his lecture? What practical
> examples have we programmed on the computer? My grades?

No. My apologies if I pushed this too far; I'm just not used
to people defending a claim based on the people they know
as opposed to their knowledge.

> > If you can find an algorithm which is guaranteed to work
> faster
> > than O(N^2) with the example I showed, I am sure Boissonnant
> > will be proud to be a co-author on the paper where you
>
> publish it.
>
> Let me put it clear: I don't know Boissonnat personally, but
> few other people who work with him. I don't know the topic
> well enough to defend it, but that what I have been taught
> and believe on.

Beliefs are for matters of religious nature. In science you
either know or don't know. What one does know one defends
by reference to the literature or by example; what one
doesn't know one either handles very carefully or looks up.

> I proposed you to contact these people if
> you have any concern about the result and if you are
> interested to figure out what behind it.

As I have hinted at a cuple of times in this thread, I have
read a few texts on computational geometry, including
Boissonant's book. Your claims are at odds with anything
I've read there.

> > If such an algorithm existed, I can assure you Boissonnant
> > would have described it in his text on geometric computations.
> > He did not mention anything of the sort.
>
> Hey, you could of course go on and make your logic in that
> sort: "such result must be wrong because Mr X did not
> publish Y";

There is such a thing as Occam's razor. If there exists a
simple, working algorithm one would expect it to be mentioned
by the people who have dozens of publications and write textbooks
on the subject. The fact that such people do *not* mention the
simple algorithms is an almost certain indicator that the
algorithms don't exist. Or at least have not been discovered
yet, which is highly unlikely (see item A) below).

> "Mr B does not *know* topic Z so his claim about
> C must be false",

Not at all. However, somebody who don't know the subject is
not likely to have contemplated the relevant aspects of a
problem, and is thus likely to have missed some detail or
misunderstood something.

> etc... That's up to up Rune. I would not
> venture to tell you whereas it will be good or bad in the
> real life, I just don't share with you that kind of logic.

Whenever a technical question comes up, there are a number of
alternatives for solutions:

A) The problem is economically relevant and a solution can
   be found. In these cases the solutions have often been
   known for decades. Radar, for example, has been known at
   least since the '30s. The technology for implementation,
   user interfaces and system integration etc have evolved,
   but the basic solution is basically unaltered since
   the first invention.

   Such problem-solution pairs are often mentioned in
   texts at the high-school or grammar school level.

B) The problem is economically relevant but no solution has
   yet been found. In these cases one must assume that lots
   of smart people have attempted to find a solution, without
   success. These are typical questions for novices to go for;
   "How can I isolate indvidual instruments in recordings of
   a band or orchestra?" There is a huge interest in a solution
   -- and has been for a long time -- but none is available.

   Of course, since no solution is known, no one kan describe
   how to solve the problem in textbooks, and anyone who tries
   to find out how the problem has been solved in the past
   finds nothing.

C) The problem is irrelevant and no one have attempted to
   solve it.

So the ability to detect 'voids' in the literature is very useful
to discover (and avoid!) dead-end projects. For instance, deciding
the species of fish based on the sonar echo is a typical dead-end
project which anyone would be wise to avoid. Doing a simple
literature search and find a total void on the subject is a
very reliable indicator to this effect.

A carreer saver, in fact, since it is impossible to excel in a
dead-end project, either because no solution can be found or
because no one are intersted in the outcome, and hence one would
never get promoted from one.

Of course, every now and then somebody come up with solutions to
previously unsolved problems, but the people who do that sort of
thing are almost exclusively extremely competent and knowledgeable,
and are fully aware of the shortcommings of the technology.

Such people are very few and very far between, so no one should
expect to become one of them; such people are only discovered
and recognized after the fact.

Rune

I was wrong about the Delaunay worst-case complexity in R^2,
it's O(N*logN).

regards,

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in
message <g76r1v$66u$1@fred.mathworks.com>...
> I was wrong about the Delaunay worst-case complexity in
R^2,
> it's O(N*logN).
>
> regards,
>
> Bruno
good