4
$\begingroup$

Roughly speaking, 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 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?

Improve this question
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Adi Shavit Jun 29 '15 at 15:11
  • $\begingroup$ Indeed, my answer said "related". $\endgroup$ – Sariel Har-Peled Jun 30 '15 at 2:01
  • $\begingroup$ 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. $\endgroup$ – Adi Shavit Jun 30 '15 at 6:01
  • $\begingroup$ 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. $\endgroup$ – Sariel Har-Peled Jun 30 '15 at 15:02

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.