Geodesic Convex Hull?

[lakshmipathyarjun6]

Would there be any interest extending the edge flip method to provide a gift wrappers algorithm over surfaces? There don't appear to be any implementations online I can find - would throw in a vote for it being a neat feature to have :)

Can possibly submit a PR at a later date myself if it's of interest!

[nmwsharp]

This sounds great! I can certainly imagine it being useful.

Do you have a particular algorithm in mind? I can imagine a few reasonable heuristics, but in general it geodesic convex hull sounds like a hard problem.

[lakshmipathyarjun6]

That...is a good question. I admittedly did not do much investigation into what the naive Jarvis march actually exploited before posting this, but after actually looking into it a teeny bit today its exploitation of the planar normal direction clearly won't work in this context.

Was also wondering if we could unpack the surface into a plane and do it that way, but then it would depend on how the unpacking is done and would break down if the region spans a cut.

So....in conclusion would like to contemplate some more after March 5 (paper deadline). Didn't realize it was an unsolved problem, but that's nice to be aware of :)

[keenancrane]

At its core, the "gift wrap" algorithm just needs the angle of each point y with respect to some given point x: https://en.wikipedia.org/wiki/Gift_wrapping_algorithm

That's something we could compute with the discrete log map. But there are still some details that would need to be worked out in the geodesic case. E.g., it's not clear how to define the "leftmost" point, even once you have all the polar angles.

[nmwsharp]

Yeah, even before getting to algorithms it's worth thinking about how you would define a geodesic convex hull of a target point set. Obviously it's easy if the points are sufficiently close in a low-curvature region, but in general it's not so simple (imagine points scattered around a topological handle).

I think one reasonable definition would be "the smallest region G \subset M which contains the target points, and has the property that for any two points p,q \in G, the shortest geodesic from p --> q is contained in G". This matches the usual definition in R^n, and seems to be well-defined on surfaces. Provably computing the convex hull defined in this way is another matter entirely :) Perhaps you could get there using some subroutine for shortest geodesics, but I'm not even sure how to do that.

Of course that being said, it would still be quite pragmatic to have an implementation of any sane algorithm, which at least outputs something reasonable in cases where the points are close together! For instance, you could:

(1) compute a center c of the distribution (2) evaluate the log map at c, and project the target points in to that log map (3) compute the traditional R^2 convex hull defined in the log map coordinates (4) project that hull back to the whole surface via the exp map

We could mostly do this using tools we already have, though the last step is a little nontrivial.

[lakshmipathyarjun6]

Errr..apologies for the naivete / newb-ness but is there somewhere I can reference what a discrete log map is?

Seems like a reasonable definition (especially with the shortest geodesic being the measurement) - it should at least reasonably differentiate the border points from the interior. Also probably naive question but I thought the geodesic is by definition the shortest path between two points?

For 4 while it may lack some guarantees, if the points on the hull determined on the log map could be mapped back to the corresponding vertices on the surface, and we know the neighboring points on the hull, could we not approximate the border on the surface just by calling the edge flip method between the neighboring points?

[nmwsharp]

Ah yeah, I jumped right in there! Basically, the log map is mapping from the surface to R^2, centered at some particular point. It has the special property that straight lines radiating from origin in the logmap are shortest geodesics from the center point. It's useful for mapping lots of 2D geometry algorithms to surfaces. See this paper for one fast PDE method for computing the logmap, as well as some applications https://nmwsharp.com/research/vector-heat-method/.

The term geodesic formally just means a "locally shortest" path, aka a "straight line" along the surface. This is often conflated with shortest geodesics, like the ones you mention. In the plane, there's only one locally-shortest path between two points, which is also the globally shortest path (a straight line). On surfaces, things are a bit more complicated: there are generally many locally-shortest geodesics between a pair of points on a surface, beyond just the shortest one (imagine two different paths wrapping around either side of a bump).

And what you mention for 4 sounds just right, I was imagining a strategy something like that :) There are also other ways to extract the this border if one is not in the mood for edge flips.

[lakshmipathyarjun6]

(9 months later...) Finally got some experience with logmaps after a recent submission, and am now wondering if something like the following could work:

First, let's assume we have a point that we know somehow lies on the convex hull, and we have already found a second point on the hull from which we have computed the bounding path from the first point. Compute a logmap with its origin at this point, with some arbitrary tangent vector direction denoting 0 degrees locally. There are three possible outcomes here: either the vector lies completely "outside" the hull bound, precisely on the hull bound (rare), or fully contained within. In the first two scenarios the points which are minimally and maximally angled away from 0 degrees (I think) should be the two possible candidates for the next hull point, and since we know where we came from that should only leave one unique candidate for selection. The third case is more tricky, but given the convexity assumption I suspect that at some point in the sweep there will be a large break between angles, so I'm wondering if we can naively just choose the points with the largest break as the candidates. Repeat this procedure until we return to the starting point (which I assume will be guaranteed to terminate).

In the case of the starting point, however, we will get two solutions. I argue that we can choose either direction to begin the march.

Finally, while one option could be to ask for the starting point, I am wondering if instead we can randomly select a point in the set, compute heat distance, and select the furthest point by geodesic distance. I am not sure if this point is guaranteed to be on the hull, but the furthest distance point from any point (border or interior) I think should exist on the border of the set.

I suspect I there might be some details I am overlooking, but curious if at least the premise seems reasonable.