<p>Alper Ungor did some nice work related to this issues of how do Delaunay refinement with alternative points. See his paper: </p>

<p><em><a href="http://www.cise.ufl.edu/~ungor/papers/offCenter.pdf" rel="nofollow">A. Ungor. Off-centers: A new type of Steiner points for computing size-optimal guaranteed-quality Delaunay triangulations. Computational
Geometry: Theory and Applications (CGTA), 42(2): 109--118, 2009.</a></em></p>

CC BY-SA 3.0
2015-06-29T15:11:00.133Z
Thanks for the reference. From an initial quick look at the paper, it seems to be concerned with replacing triangle circumcenter vertices with *off-center* vertices to improve the triangulation. IIUC, taking the mid-point of the *encroached* segment still happens in the proposed algorithm.
Adi Shavit
CC BY-SA 3.0
2015-06-30T02:01:05.160Z
Indeed, my answer said "related".
Sariel Har-Peled
CC BY-SA 3.0
2015-06-30T06:01:19.437Z
Is there *indeed* a relation in the rational for selecting segment mid-points and triangle circumcenters? If there is a common rational than perhaps some general rule could be inferred from the Ungor off-center approach.
Adi Shavit
CC BY-SA 3.0
2015-06-30T15:02:13.340Z
The rational is that inserting the mid edge point generates two new protecting disks, that are of equal radius -- thus this is the choice that balance these two quantities. As Alper work suggest - you can try and make a more careful choice and things might work better. For example, you might know that you have to refine things only one side of the segment, so putting the new point closer to this side, would result in less points inserted later.
Sariel Har-Peled
CC BY-SA 3.0
2015-06-28T15:47:05.287Z
2015-07-01T11:25:46.787Z
2015-07-01T11:25:46.787Z
Sariel Har-Peled
<p>Roughly speaking, in <a href="http://www.cs.berkeley.edu/~jrs/papers/2dj.pdf" rel="nofollow">Ruppert's Delaunay Triangulation refinement algorithm</a>, so called <em>encroached edges</em> are split until no more encroached edges remain.  </p>

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

<p>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). </p>

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

<p>Another way to ask this is: Are there split points that are <em>better</em> (by some interesting measures) than the <em>a-priori</em> selected midpoints?</p>

<cg.comp-geom><computational-geometry><delaunay-triangulation>
Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm
Adi Shavit
# Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm

(Asked by: username_0 on 2015-06-10)

Roughly speaking, in [Ruppert's Delaunay Triangulation refinement algorithm](http://www.cs.berkeley.edu/~jrs/papers/2dj.pdf), 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* are 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* (by some interesting measures) than the *a-priori* selected midpoints?

**Tags:** cg.comp-geom, computational-geometry, delaunay-triangulation


---

## 1 answers

### Answer by username_1 on 2015-06-28. Score: 2 | Accepted answer

Alper Ungor did some nice work related to this issues of how do Delaunay refinement with alternative points. See his paper:

*[A. Ungor. Off-centers: A new type of Steiner points for computing size-optimal guaranteed-quality Delaunay triangulations. Computational
Geometry: Theory and Applications (CGTA), 42(2): 109--118, 2009.](http://www.cise.ufl.edu/~ungor/papers/offCenter.pdf)*

> **Comments:**
> **username_0**: Thanks for the reference. From an initial quick look at the paper, it seems to be concerned with replacing triangle circumcenter vertices with *off-center* vertices to improve the triangulation. IIUC, taking the mid-point of the *encroached* segment still happens in the proposed algorithm.  
> **username_1**: Indeed, my answer said "related".  
> **username_0**: Is there *indeed* a relation in the rational for selecting segment mid-points and triangle circumcenters? If there is a common rational than perhaps some general rule could be inferred from the Ungor off-center approach.  
> **username_1**: The rational is that inserting the mid edge point generates two new protecting disks, that are of equal radius -- thus this is the choice that balance these two quantities. As Alper work suggest - you can try and make a more careful choice and things might work better. For example, you might know that you have to refine things only one side of the segment, so putting the new point closer to this side, would result in less points inserted later.  

---

