Prev: Coherence estimate using multi taper
Next: Heligman and Pollard + LMFsolve
From: Jveer on 8 Oct 2009 16:43
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?
From: Jveer on 8 Oct 2009 17:16
i meant * way too SLOW
From: Rune Allnor on 8 Oct 2009 18:20
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
From: Jveer on 8 Oct 2009 21:20
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: Bruno Luong on 9 Oct 2009 02:01
"Jveer " <jveer(a)jveer.com> wrote in message <ham34i$hm4$1(a)fred.mathworks.com>...

>
> 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?

Your description remains muddy. What is "very large n"? What is slow? Which Matlab version are you runing? Do you have repeat points (or almost?) in your data. In the latest releases, DELAUNAYN use a C or fortran library from "qhull" group, which is one of the most reliable with decent speed, and already compiled. So what *else* do you want to MEX? What make you believe you can do better than people who devote their life for this topic?

For N=10000 (10^4) uniform random points in R^3, it takes less than a second on my PC (2009B).

The theoretical worse complexity is O(N^2) in R^3. In practice, it's slightly more than O(N) as showed in the below code:

>> n=2.^(10:16);
t = zeros(size(n));
for k=1:length(n)
P=rand(3,n(k));
tic; tetr=delaunayn(P'); t(k)=toc;
end
t
P=polyfit(log(n),log(t),1);
fprintf('time = O^%g\n',P(1));
loglog(n,t);

t =

0.0962 0.2053 0.4423 0.9752 2.0511 4.1500 8.5410

time = O^1.08233
>>

% Bruno
 |  Next  |  Last
Pages: 1 2
Prev: Coherence estimate using multi taper
Next: Heligman and Pollard + LMFsolve