Generating Convex Polygonal Neighborhoods from Triangulations of Discrete Pointsets

Question

The wellknown Delaunay Triangulation $DT$ has as a straight line dual the also wellknown Voronoi Diagram $VD$.

Both are most commonly defined in the Euclidean plane and are primarily beneficial for solving problems related to geometric proximity, but they have also been generalized to higher dimensions, different distance measures and also for problems related to $n$-th nearest neighbor queries up to farthest neighbor queries.

This question is however only related to the planar euclidean case.

Question:

Have analogous "tandems" of triangulations and convex polygonal neighborhoods of discrete pointsets in the euclidean plane already appeared, resp., investigated where the corners of the polygonal neighborhoods are not the circum centers of triangles (which can also be outside of triangles e.g. in random triangulations), but other special points associated to triangles, like the ones listed in the ETC (of which the incircle center seems the most interesting choice because it is guaranteed to be inside the most degenerated triangle with nonzero area and, because it seems to generate polygonal neighborhoods with longer short sides)?

I am especially interested in results related to optimality criteria that the selection of specific triangle points (apart from the circum center) implies for the generated polygonal diagrams.


Additional thoughts:

constructing the polygonal regions from other triangle points might also have positive impact on the convergence rate of generating centroidal $VD$s; the triangulaton of the generated centers of gravity would however still be the $DT$ and after having reached good convergence, switching back to circumcenters could be done.

The question would then be, which of the special triangle points gives better performance improvements: incircle center or centroid? Further question in that respect: can convergence of the algorithm be improved by initially taking as new points for the subsequent $DT$ not the centers of gravity of the generated polygonal regions, but rather the centers of the largest enclosed circles?

Answer 1

This doesn't satisfy all your criteria, but still it might help to look at the weighted Voronoi diagram (VD), and its dual, the weighted Delaunay triangulation (DT), for these are examples of "tandems of triangulations and convex polygonal neighborhoods," distinct from the DT & VD. Circumcircles in unweighted Delaunay triangulations are replaced with orthocircles. See the work by Gary Miller and Don Sheehy, from which the figure below is taken. The weighted Delaunay triangulation is still the projection of a convex polytope in one higher dimension, and so remains piecewise-linear.

---

         
          ^{Fig.1: A weighted Voronoi diagram with weights indicated by disks.}

---

Miller, Gary L., and Donald R. Sheehy. "A new approach to output-sensitive Voronoi diagrams and Delaunay triangulations." Proceedings 29th Symposium on Computational Geometry. ACM, 2013. (arXiv abs)