I am trying to implement a mesh generation algorithm. Input to the algorithm is a set of constraints(imposed on output mesh) called Piecewise Linear Complex(PLC) which is a collection of vertices $V\subset\mathbb R^3$, edges $E=\{(a,b)|a,b \in V\}$ and triangles $T=\{(\alpha,\beta,\gamma)|\alpha,\beta,\gamma \in V\}$.

In one of the stages of the algorithm I need to perturb a vertex $v$ along an edge $e$, similarly I also need to perturb a vertex along the plane of a triangle $t$. Perturbation should be the smallest non-zero disturbance which will preserve Delaunay edge property for all edges in $E$.

My assumed definition of a Delaunay edge is: An edge is Delaunay, iff there exists a circumsphere of its endpoints not containing any other vertex inside it.

So I have two problems:

Perturbation along an edge:

In this case, I think that I need to shift the vertex by a small step along both directions on the edge and test in which case Delaunay property of all edges is preserved. But how should I decide the step size?

Perturbation along a triangle:

Extending my basic approach to 2 dimensions, my step will be a 2D tuple now and again I don't know how to decide its value?

Since perturbation should be the smallest possible disturbance, it seems to me that step size will be different for different machine representations.

So, my questions are:

  1. Is there any other more efficient(requiring lesser number of operations) approach for this vertex perturbation problem?

  2. If not, can we decide step size which can work reliably regardless of machine representation?

P.S.: Reference paper for this problem is here.(Section 6: Removing local degeneracies)

  • $\begingroup$ Your question is not very clear to me. You first talk about line and a point. Then you are talking about edges. How the edges are formed? I believe the step size should be part of an algorithm should not be machine dependent. But things are not clear to me and can't answer it properly. $\endgroup$ Commented May 15, 2014 at 15:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.