Prev: Coherence estimate using multi taper
Next: Heligman and Pollard + LMFsolve
From: Bruno Luong on 9 Oct 2009 02:14
Sorry should be:

fprintf('time = O(n^%g)\n',P(1))

t =

0.1027 0.2188 0.4458 0.9682 2.0011 4.0891 8.4991

time = O(n^1.06165)
>>

% Bruno
From: Rune Allnor on 9 Oct 2009 04:56
On 9 Okt, 03:20, "Jveer " <jv...(a)jveer.com> wrote:
> Rune Allnor <all...(a)tele.ntnu.no> wrote in message <b636c673-7327-4e75-8243-64ffe57f3...(a)f10g2000vbf.googlegroups.com>...
> > On 8 Okt, 23:16, "Jveer " <jv...(a)jveer.com> wrote:
> > > i meant * way too SLOW
>
> > Two comments:
>
> > 1) Higher-dimensional geometric algorithms *are* slow. Don't be
> >    surprised if the complexity goes something like O(f(N)^k)
> >    where k is the number of dimensions. With a bit of luck,
> >    f(N) < N, but don't rely on it.
> > 2) For non-specific number of dimensions, a lot os stuff that
> >    could have been optimized by a compiler, has to remain
> >    non-optimized. If you have a specific application in mind,
> >    write a special purpose application that is optimized
> >    for that problem.
>
> > Rune
>
> thanks for the reply Rune.
>
> this is how i use it : tetr=delaunayn(P',{'QJ'}) where P is a 3Xn matrix. n is usually very large.
>
> delaunay3 is slower. delaunaytri just hangs and i have to force quit matlab.i considered writing mex function but i havent got a clue how delaunayn works.  

Well, I'm currently writing a triangulator for 2D data.
Believe me, that's not something that is done in a hurry.

Just use what you have. Accept that computations take time.
Leave the computer to work in your free time; overnight,
through weekends, in vacations etc. No need for you to
babysit the computer while it does its thing.

Rune
From: Damian Sheehy on 9 Oct 2009 08:49
DelaunayTri is generally 3-4 times faster than DELAUNAY3/DELAUNAYN as they
use different underlying algorithms.
If your input data is highly degenerate, which I suspect yours is, the
performance is reduced as additional computation is performed to guarantee
robustness and the integrity of the output.
Examples of degenerate data include data in a grid, prismatic distribution
of points, points lying on the surface of a cylinder etc.
The performance of DelaunayTri when triangulating degenerate datasets was
improved in release R2009b.
This performance can further improved by shuffling the points prior to
insertion.
For example, given a set of points X, shuffle them as follows;
k = randperm(num_points)';
X = X(K,:);
dt = DelaunayTri(X);
For highly degenerate datasets the performance of DelaunayTri is no better
than DELAUNAY3/DELAUNAYN.
However, DelaunayTri is guaranteed to be robust and to provide a valid
triangulation output in the presence of degeneracies.
Based on my experience (~20 yrs) with Delaunay triangulations you will not
get much better performance than what you are seeing without compromising
robustness/integrity, and that's not practical in a commercial setting.

For dimensions higher than 3D you hit the "curse of dimensionality", as
others have pointed out, as size and complexity grows exponentially.
In general the practicality of Delaunay triangulations maxes out long before
you reach 10D.

If you would care to share particulars (data/requirements) about your
problem off-line I would be more than happy to provide advice; feel free to
contact me directly.


Best regards,


Damian

"Jveer " <jveer(a)jveer.com> wrote in message
news:ham34i$hm4$1(a)fred.mathworks.com...
> Rune Allnor <allnor(a)tele.ntnu.no> wrote in message
> <b636c673-7327-4e75-8243-64ffe57f3301(a)f10g2000vbf.googlegroups.com>...
>> On 8 Okt, 23:16, "Jveer " <jv...(a)jveer.com> wrote:
>> > i meant * way too SLOW
>>
>> Two comments:
>>
>> 1) Higher-dimensional geometric algorithms *are* slow. Don't be
>> surprised if the complexity goes something like O(f(N)^k)
>> where k is the number of dimensions. With a bit of luck,
>> f(N) < N, but don't rely on it.
>> 2) For non-specific number of dimensions, a lot os stuff that
>> could have been optimized by a compiler, has to remain
>> non-optimized. If you have a specific application in mind,
>> write a special purpose application that is optimized
>> for that problem.
>>
>> Rune
>
> thanks for the reply Rune.
>
> this is how i use it : tetr=delaunayn(P',{'QJ'}) where P is a 3Xn matrix.
> n is usually very large.
>
> delaunay3 is slower. delaunaytri just hangs and i have to force quit
> matlab.i considered writing mex function but i havent got a clue how
> delaunayn works. i did a 'edit delaunayn' and noticed it uses qhullmx
> which cannot be edited.
>
> are there any common speedy alternatives to the delaunayn functionality?


From: Luigi Giaccari on 11 Oct 2009 12:53
"Jveer " <jveer(a)jveer.com> wrote in message <halisn$s3s$1(a)fred.mathworks.com>...
> as most of you probably already know the in built 'delaunayn' function is way too also for realistic practical applications.
>
> does anyone know of any alternatives with the same functionality?
>
> how about creating a c mex version of it?

The data you sent me is structured, I told you delaunayn is a waste od time.

Use instead:

http://www.advancedmcode.org/structured-tedrahedral-mesh-generation.html

Regards

Luigi

http://www.advancedmcode.org
First  |  Prev  | 
Pages: 1 2
Prev: Coherence estimate using multi taper
Next: Heligman and Pollard + LMFsolve