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.]

Advertisements

5 responses to “Convexity Using Metric Balls

  1. If your manifold is an open unit disk in the Euclidean plane (surely a nice space for convexity problems) then the half-disk is not an intersection of metric balls. (It is an intersection of metric balls in the whole plane but you need the centers of the balls to be far away.)

    So if you want the ball hull to be the convex hull you are going to have to impose some conditions that rule out this case.

  2. Ah, but if your manifold is the hyperbolic plane, which is not bounded, then no half-plane is an intersection of unit balls.

    This is just David’s example with a metric.

    • The balls I’m using are actually any arbitrary metric ball, not just unit balls. I also forgot to mention that any set I’d like to hull has bounded diameter.

      Incidentally, I just had an a-ha moment while I was drafting this reply. It’s not to do with this particular issue, but it still made me realize something. So thanks!

    • And Suresh just burst my bubble. But that’s ok.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s