About complexity of Gabriel Graphs Bis...

aupetit aupetit at dase.bruyeres.cea.fr
Thu Mar 28 08:41:55 PST 2002

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
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:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.

More information about the Compgeom-announce mailing list