Path: news.mathworks.com!newsfeed-00.mathworks.com!newsfeed2.dallas1.level3.net!news.level3.com!postnews.google.com!t54g2000hsg.googlegroups.com!not-for-mail
From: Rune Allnor <allnor@tele.ntnu.no>
Newsgroups: comp.soft-sys.matlab
Subject: Re: finding minimum distance in a set of points
Date: Sat, 2 Aug 2008 08:30:35 -0700 (PDT)
Organization: http://groups.google.com
Lines: 58
Message-ID: <8b35bb69-3422-4ee2-9ded-cef187bd6299@t54g2000hsg.googlegroups.com>
References: <g6v8fd$ntc$1@fred.mathworks.com> <bc2dfbf2-bf15-49ed-aac3-dab1d24e6c3b@34g2000hsh.googlegroups.com> 
NNTP-Posting-Host: 212.17.141.54
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
X-Trace: posting.google.com 1217691035 27063 127.0.0.1 (2 Aug 2008 15:30:35 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sat, 2 Aug 2008 15:30:35 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: t54g2000hsg.googlegroups.com; posting-host=212.17.141.54; 
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET 
Xref: news.mathworks.com comp.soft-sys.matlab:483283



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