About complexity of Gabriel Graphs Bis...

[aupetit]

Hello all,

thank you for your answers, but I have to precise my query:

I need to compute the Gabriel Graph in high dimension d,
and for d>2, the complexity of Delaunay graph is no more O(n.log(n))
but O(n^|d/2|) [Fortune1992]  (with |x|=ceil(x)) hence it becomes
intractable
for large d to compute Delaunay graph and extract Gabriel graph from it.

The brute force algorithm I have is O(d.n^2) and I wonder if it exists a

better one "for d>2".

Thanks

Michael




-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.