I know that delaunay triangulation can be extended into arbitrary dimensions by solving the convex hull problem in $(p+1)$ dimensions and projecting the lower hull into dimension $p$ to obtain a mesh in dimension $p$. However, this approach is asymptotically $\Omega({n}^{{p}/{2}})$. I was wondering if there are any other algorithms to produce arbitrary dimensional meshes that can be implemented faster. If so, what are they, how do they work and what is their asymptotic runtime (in terms of the number of mesh points)?

  • $\begingroup$ What is $\Omega$? What is $d$? $\endgroup$ – David Ketcheson Jan 15 '12 at 9:00
  • $\begingroup$ Using asymptotic notation (see Introduction to Algorithms 3rd Edition by Cormen et al.), it roughly means that the runtime for large problem sizes (large point sets) is at least ${n}^{p/2}$, where n is the cardinality of the point set. $\endgroup$ – Paul Jan 15 '12 at 16:37
  • $\begingroup$ Thanks. But I found an explanation here that says something different: en.wikibooks.org/wiki/Data_Structures/… That says that what you wrote only means it is at least $cn^{p/2}$ where $c$ is some constant. Also, since both $n$ and $p$ are arbitrary, can you specify in which one this is asymptotic? $\endgroup$ – David Ketcheson Jan 15 '12 at 19:15
  • $\begingroup$ @DavidKetcheson The statement is only a lower bound. The asymptotic statement should be interpreted as being for any given $p$, there is $n_0$ and $c>0$ such that the algorithm takes at least $c n^{p/2}$ for all $n > n_0$. $\endgroup$ – Jed Brown Jan 15 '12 at 20:00
  • $\begingroup$ @Paul Do you want a Delaunay mesh? (If the problem is anisotropic, then you would not want Delaunay.) What quality constraints? Note that Delaunay in 3D can still have quite bad elements. $\endgroup$ – Jed Brown Jan 15 '12 at 20:00

How about; Watson, D.F. Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes. Comput J 24, 167–172 (1981).


If I understood it, it should be $\mathcal{O}\left(n^{\frac{2p-1}{n}}\right)$, isn't that better then $Ω\left(n^{p/2}\right)$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.