Roughly, in Ruppert's Delaunay Triangulation refinement algorithm, so called encroached edges are split until no more encroached edges remain.

The algorithm specifies splitting the edges at their midpoint (except in the case of small input angles where concentric circular shells as suggested. This question is unrelated to these cases.)

In certain domains, given a segment, there are points on the segment that I would prefer to split on that are not necessarily the midpoints (unrelated to the concentric shell trick). These points are chosen based on some domain specific underlying data (considerations beyond the graph structure the algorithm is aware of).

  • What are the implications of splitting on non-midpoints?
  • What needs to be taken into consideration when selecting among several non-midpoint candidates?
  • Does splitting on non-midpoints affect any of the convergence properties of the algorithm?

Another way to ask this is: Are there split points that are better than the a-priori selected midpoints?


In Rupert's refinement algorithm, if the circumcenter of a "skinny" (poor quality) triangle were inside the domain and its location is "sufficiently" far away from other points in the triangulation, the algorithm terminates. When the circumcenter is inserted, it is at least a certain distance from all other points (equal to the circumradii), so it will eventually run of space to add more points. Luckily, the ratio of the circumradii and length of the smallest side of a triangle is a function of the smallest angle in the triangle. Therefore, if a skinny triangle is defined as a triangle whose ratio is greater than 1 (corresponds to a minimum angle of 30 degrees), the algorithm is guaranteed to terminate.

But what if the circumcenter is outside the domain? That is when the midpoint on the "nearest" boundary edge is inserted. When the midpoint is inserted, it introduces two short edges whose length is equal the half the length of the original edge. In addition, all points within the diametrical circle of the original edge are deleted so that there are no "even-shorter" edges introduced. And because these two new edges may be shorter than the previous shortest edge in the mesh, during the next step, we should introduce the circumcenter only if the ratio (cumcumradii : shortest length) is greater than some quantity that is strictly greater than 1. In the pdf you shared, it is shown that the ratio should be $\sqrt2$.

If you inserted a point not on the midpoint, but somewhere else on the edge, you will create an edge shorter then half the length of the boundary edge. This edge may be much shorter than the current shortest edge in the mesh. So the ratio that guarantees termination will be greater $\sqrt2$.

To answer your specific questions: 1. Implication: weaker termination guarantee 2. The length of new edges created should be considered. If they all happen to be large, you can happily add a non-midpoint vertex into the mesh. If the boundary edge is a light year long, and other mesh edges are orders of magnitude shorter, you can split the edge almost anywhere ... almost (see below). 3. Yes, splitting on non-midpoints affects termination guarantees.

BUT .....

Alper Ungor's paper attempts to insert off-circumcenter points instead of the circumcenter.

And this paper also allows for insertion of non-midpoint vertices into the mesh. But in the limiting case, it reverts to mid point insertion.

  • $\begingroup$ It's been a couple of years since I've asked this. But this seems to be a good answer. Thanks! $\endgroup$ – Adi Shavit Aug 2 '17 at 21:23

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.