Computing the iso-Delaunay region associated to a flat triangulation

[videlec]

According to Joshua P. Bowman "Teichmueller geodesics, Delaunay triangulations and Veech groups", to any flat triangulation (T, ζ) the set of matrices M in SO(2) \ SL(2,R) = H such that (T, M ζ) is Delaunay form a hyperbolic polygon of finite area (each edge of the triangulation determines a half-space).

Note that this polygon might be empty if (T, ζ) can not be turn in Delaunay form.

We should have functions

• that to a flat strictly quadrilateral computes the corresponding half-spaces
• make intersection of the set of hyperbolic polygon for all quadrilaterals in a given triangulation

[videlec]

@saraedum It is not clear to me whether we want this in sage-flatsurf or pyflatsurf. I don't like so much the datastructure of sage-flatsurf when it comes to edge flipping (which is all what this iso-Delaunay triangulations is about).

[videlec]

One optimiztion question. Each iso-Delaunay region is written as half-space intersections. These sets of half-spaces for two neighboring regions are almost the same. Typically, only 5 half-spaces differ corresponding to the edges adjacent to an edge flip. In the iso-Delaunay tesselation, it would be interesting to optimize the region computation by using this fact.

[wphooper]

Two students I was working with last summer, Zhi Heng Liu and Seth Foster, coded the iso-Delaunay tiling last summer. I've been negligent about getting it in Sage. It works even for dilation surfaces.

[saraedum]

Two students I was working with last summer, Zhi Heng Liu and Seth Foster, coded the iso-Delaunay tiling last summer. I've been negligent about getting it in Sage. It works even for dilation surfaces.

Is there code available somewhere online?

[saraedum]

@saraedum It is not clear to me whether we want this in sage-flatsurf or pyflatsurf. I don't like so much the datastructure of sage-flatsurf when it comes to edge flipping (which is all what this iso-Delaunay triangulations is about).

I think this should live in sage-flatsurf. It's true that edge-flipping is easier in libflatsurf but we don't actually need edge flipping for this step yet. We need to determine whether an edge can be flipped though which is triangle_flip(..., test=True). We might find performance issues due to the structure in sage-flatsurf but we can still worry about these once we have them.

[wphooper]

I'd be more comfortable putting it in sage-flatsurf anyway. I'll try to get to this in the next week or two.

The code is in some Jupyter notebooks that the students created. It makes use of the Hyperbolic geometry packages in Sage. We needed "canonicalization" for dilation surfaces. This is some stuff I mostly wrote that will need also to go into sage-flatsurf.

[saraedum]

So, @sfreedman67 has an implementation of this as well (without the dilation surface part.) It's similarly in some Jupyter notebooks. We were getting started on getting this into sage-flatsurf for #157 during a conference in Bordeaux last week and had planned to work on this more during this week while we're both in Orsay.

I started to work on some hyperbolic geometry code in #158 since apparently the implementation in sage has some problems. (@videlec @slel could you elaborate?)

We made some notes on the eventual interface that we want to implement at https://hackmd.io/@EGlfdaUNRiSIIb7HvoU0rw/r1uAwLEE9

Could we have a call about this to discuss how we want to continue here? @wphooper @videlec @slel @sfreedman67
(Any day but Thursday works for me, 10am-2am Paris time.)

[sfreedman67]

I'd think I'm pretty free Tuesday (not Paris evening) and Wednesday

[videlec]

The problems with sage implementation of things is that

• each model has its system of coordinates and implementation of things
• there is no convex hull computation
• coordinates are dealt with in a very symbolic way (you very often end up with things in the symbolic ring)
• there are some bugs
• choosen names are not very nice

I believe that we can try to use it to some extent and improve what needs to be.

[wphooper]

@saraedum Did you mean 10am-2am or 10am-2pm? If you meant pm, then I can get up early one day to meet you at 1-2pm Paris Time Wednesday. But if you really meant 2am, then I could do 7pm Paris time on Tuesday.

We did run into some issues with SymbolicRing with the hyperbolic geometry. If I recall correctly, we didn't do anything smart about that, just used the code and forced things to go back into the correct ring after calling the hyperbolic geometry package.

[saraedum]

Ok. Let's meet at 7pm Paris time on Tuesday then. We'll meet at https://bbb.imo.universite-paris-saclay.fr/b/jul-2bp-hjt-ery.

[saraedum]

Some results from that meeting:

• We'll continue with the hyperbolic plane implementation. Eventually, we'll try to get it into SageMath as an alternative implementation and then deprecate the existing one.
• We should look into making the approach work for (half-)dilation surfaces. (Someone has to check whether our codes still work there.)
• We should maybe support half-dilation surfaces in libflatsurf.

[videlec]

* We should maybe support half-dilation surfaces in libflatsurf.

Let's discuss a wishlist/plan at flatsurf/flatsurf#302

[sfreedman67]

• We should look into making the approach work for (half-)dilation surfaces. (Someone has to check whether our codes still work there.)

@wphooper @saraedum @videlec @slel Is anyone interesting in hopping on a Zoom call early next week to discuss this?

[wphooper]

I'd be willing to discuss on Zoom on Tuesday or Thursday next week. I'm free most of those days except 11-12 on Tuesday (NY time).

Here are some comments that might be useful if you want to put half-dilation surfaces in libflatsurf, and perhaps for iso-Delaunay.

1. A triangle with edges labeled 1,2,3 is determined up to the action by the half-dilation group is determined by its triple of slopes. A triangulated half-dilation surface is then determined by the slopes of the sides together with the combinatorics by which the triangles are glued. The orientation of a triangle depends on the cyclic ordering of the slopes of the sides of the triangle.
2. Given any quadrilateral (which is non-degenerate in the sense that no two adjacent sides have the same slopes), there is a real Mobius involution with the property that it swaps the slopes of opposite sides and also swaps the slopes of the diagonals. Note that a Mobius involution is determined by two pairs of swapped values, so this comment puts non-trivial constraints on the slopes of the edges and diagonals of a quadrilateral.
3. A Mobius involution naturally acts by isometry on H^2, either by a 180 degree rotation or a reflection (in which case the action on the upper half plane is obtained using complex conjugation). A quadrilateral is convex if and only if the involution it determines is a reflection. Furthermore, given a Delaunay triangulation, its iso-Delaunay cell is the intersection of the half-spaces containing the imaginary number i, taken over all convex quadrilaterals formed by two adjacent triangles in the triangulation.

I guess I'm saying this because considering half-dilation surfaces seems to give this beautiful structure to the iso-Delaunay regions. So, I think in some sense this is the most natural setting for the algorithm. Bowman's paper is great, but the identification between the hyperbolic plane and triangulations seems less natural than what I am describing above (which is a different way to move between the geometries). This stuff will appear shortly in a paper I am writing jointly with Zhi Heng Liu and Seth Foster (who coded this other version of the algorithm that works for half-dilation surfaces). It would be great to combine to have the best possible algorithm...

Perhaps slope coordinates would be useful for libflatsurf?

[sfreedman67]

I'd be willing to discuss on Zoom on Tuesday or Thursday next week. I'm free most of those days except 11-12 on Tuesday (NY time).

Tuesday works for me as well. Could we do 9am or 10am NY time?

[sfreedman67]

I'd be willing to discuss on Zoom on Tuesday or Thursday next week. I'm free most of those days except 11-12 on Tuesday (NY time).

Tuesday works for me as well. Could we do 9am or 10am NY time?

How does does sound @wphooper @saraedum @videlec @slel ?

[saraedum]

We're having our regular weekly call Tuesday at 8pm Germany time. Maybe we should discuss this then? (Otherwise, I am also fine with the proposed 9am NY time.)

[sfreedman67]

Maybe we should discuss this then?

I like that idea

[wphooper]

That time works fine for me too.

[saraedum]

We'll meet at https://us02web.zoom.us/j/85184754957?pwd=SEpJaGRmc3c0MjFGcUw3YTlqRWtQdz09