Tag Archives: hull

Convexity Using Metric Balls

I figure that I owe my readers a technical post, so while I’m riding home on the bus, I’ll write it up. This occurred to me when I was trying to figure out what to do on the ride. I have a nice gadget with a WordPress app, so why not?

The project that I’m working on now involves defining a notion of convexity for a non-Euclidean space. There are any number of difficulties that you can run into when you attempt to define convexity on an arbitrary space, but I do have a few guarantees:

  • I’m on a manifold, so shapes make “sense,” albeit in a squishy way
  • I don’t have any limitations of convexity; that is, I can make a convex set as large as I like
  • Metric balls are convex

So now I want to define a convex hull of a set of points in this space. I can do this in one of two ways. I can say that the convex hull is the convex set of minimal volume containing the set, or equivalently, that it is the intersection of all convex sets containing the set.

I’d like to say that the intersection of all metric balls containing the set is the same as the convex hull (not just any convex superset of the set, mind you; specifically metric balls that are supersets of the set in question). I don’t necessarily need this lemma to be true, but it would be nice. The way to show that two sets are equivalent is usually to say that one contains the other, and vice-versa.

It’s quite trivial to show that (in this space) the intersection of all metric balls that contain the set also contains the convex hull. Metric balls are, after all, convex. It’s trickier (to me) to show that the converse would also be true; that is, that the convex hull of a set also contains the intersection of all metric balls that contain the set. Any ideas?

[Update: apparently there’s a construction called a ball hull that is exactly the intersection of all metric balls containing a set. Perhaps it is essentially different from a convex hull.]