@PeterTaylor thanks, but see my first comment to David above: "The reason I care about necklaces and not bracelets is because I don't want to quotient by reversal of the paths, paths are oriented". I see now that David has assumed quotient by reversal in his answer, but he could easily modify it to account for both possibilities.

Another neat result of the chord diagram approach is that one can immediately see which paths are "non-returning" (like path number 2 for 2D and paths number 3 and 4 in 3D in the image above) by checking whether the chord diagram is connected. The number of connected diagrams for different n is given in OEIS A018225 and, starting from n=2, is 1, 2, 6, 31...

I was about to post this as an answer right now, when I came across your answer. You did get to a solution of the problem (can you confirm that your approach would give A007769?) so I am happy accept your answer if you updated it with the additional information.

Hi David, thanks for the awesome answer. There has been in the meantime substantial discussion about this problem on the /r/math subreddit, see reddit.com/r/math/comments/1f7ui06/… I did figure out the connection to chord diagrams and realized that what I am looking for is OEIS A007769 "Number of chord diagrams with n chords; number of pairings on a necklace". Starting from n=2, we get 2, 5, 18, 105... The reason I care about necklaces and not bracelets is because I don't want to quotient by reversal of the paths, paths are oriented.

I have not, because I am not familiar with the exponential map, but I will look into it, thank you. It sounds useful because geodesic circles/distance circles do have constant geodesic curvature (and are therefore perimeter-extremizing) in surfaces of constant Gaussian curvature.

I am looking for an expression for Pmin at least like the one that I give above for Pgeo, with the first nontrivial order (presumably going as AK), and ideally a notion of what kind of terms would come at higher orders in the expansion (higher powers of AK, derivatives of K...). Actually I suspect that the first order in Pmin will coincide with the first order of Pgeo I give above, i.e. as you make the perimeter-minimizing disk containing point p smaller and smaller its boundary becomes more and more similar to a distance circle centered at p. But I would like a (reference to) a proof of this.

I see, sorry for the confusion. I used the terminology that came in the Wikipedia page for Bertrand–Diguet–Puiseux theorem I linked above, and in the Wikipedia page for "geodesic circle" (although the latter says that this term is also sometimes used to refer to circles of constant geodesic curvature). The formula I gave above is not reproduced from Bertrand et al., rather derived from their two results for the limiting values of the area and the perimeter of the "distance circle", listed in the Wikipedia page of the theorem linked above.

No, it's the region enclosed by a geodesic circle. The geodesic circle of radius r centered at a point p is the set of all points whose geodesic distance from p is equal to r. But for an arbitrary surface, the geodesic disk thus defined is not necessarily the perimeter-minimizing disk, in the sense of the isoperimetric inequality. I am trying to find out if there is something that can be said about the mininal perimeter of infinitesimally small disks at a a surface, based on the local curvature of the surface.