About complexity of Gabriel Graphs Bis...
aupetit at dase.bruyeres.cea.fr
Thu Mar 28 08:41:55 PST 2002
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
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".
The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce