I am conducting an experiment comparing some 2d plane spanner algorithms in C++ using CGAL. Most of the algorithms start with the standard Delaunay triangulation, so I have been using Delaunay_triangulation_2 without issue. The last few algorithms, however, utilize other convex shapes for the Delaunay condition, such as an oriented equilateral triangle (Triangular Distance or TD) or an oriented square (L1). I wish the use something as close as possible to Delaunay_triangulation_2 for experimental consistency. I have also tried the half-theta graph from the cone spanners package, but I found it to be unbearably slow compared to the Delaunay triangulation on the same point sets.
My first attempt involved creating a TriangulationTraits_2 class that implements the Side_of_oriented_circle_2 functor with my desired metric. This proved difficult because this functor receives a face on which to test the empty circle property, whereas the "Delaunay condition" for the new metrics involves edges: an edge is Delaunay if no point lies within the specified shape that circumscribes that edge. My solution was to test each edge of the given face. This is expensive but on the surface seems to work, but it resulted in precondition fails for invalid flips. This makes sense because we know that these metrics may not result in valid triangulations. At this point, I noticed this blurb on the Delaunay_triangulation_2 page:
Changing this predicate type allows the user to build Delaunay triangulations for different metrics such that L1 or L∞ or any metric defined by a convex object. However, the user of an exotic metric must be careful that the constructed triangulation has to be a triangulation of the convex hull which means that convex hull edges have to be Delaunay edges. This is granted for any smooth convex metric (like L2) and can be ensured for other metrics (like L∞) by the addition to the point set of well chosen sentinel points.
By now, I'm figuring that I need to write my own class to act as a wrapper around the CGAL triangulation: either to handle edges that are invalid according to the new metric but need to be included still because CGAL's Triangulation must remain valid, or handle the sentinel points mentioned previously. I chose the former option. Using the source code for Delaunay_triangulation_2, I created my own subclass of Triangulation_2 and started messing around with the flipping algorithm to detect when an invalid flip may occur or an infinite flip to mark the edge as invalid but stop the propagation of the flip, but I haven't been entirely successful, nor am I convinced that the flipping algorithm is even guaranteed to work for alternative metrics.
Can anyone offer any thoughts or ideas about how to accomplish this or the validity of the flipping algorithm under non-smooth metrics?