11
$\begingroup$

Let $K_1$, $K_2$ be two convex compact sets in $\mathbb{R}^d$, and $p_1,p_2$ be their barycenters. Is it true that the distance between $p_1$ and $p_2$ does not exceed a Hausdorff distance between $K_1$ and $K_2$? If not, maybe there is some weaker estimate, say, uniform continuity of the map (convex body)$\rightarrow$ (its barycenter) for bodies inside, say, unit ball?

UPDATE. As Anton pointed out, the answer is obviously no, just take rectangle $\varepsilon\times 1$ and divide it by diagonal onto two triangles. Let me ask another question: is the barycentre of a closed $\varepsilon$-neighborhood close to the barycentre of initial body uniformly for all bodies inside unit ball?

Improve this question
$\endgroup$
6
  • $\begingroup$ Yes, the barycenter depends continuously on the Hausdorff metric. You should be able to show this directly from the definition of the barycenter as the expected value of a point in $R^n$ with respect to the uniform probability density on $K$. $\endgroup$
    – Deane Yang
    Commented May 7, 2012 at 19:25
  • $\begingroup$ @Deane: You're right, but I think you're implicitly using that the Hausdorff distance and the distance defined as the volume of the symmetric difference of two convex bodies define the same topology on the space of convex compact sets. It may be worthwhile to point this out. $\endgroup$
    – alvarezpaiva
    Commented May 7, 2012 at 19:40
  • $\begingroup$ @alvarezpaiva: sorry, what volumes are you saying about? Bodies may even have different dimensions. $\endgroup$
    – Fedor Petrov
    Commented May 7, 2012 at 19:47
  • $\begingroup$ @Deane: you mean something like "if $K_1$ and $K_2$ are on Hausdorff distance $c$, then the probability [for a random point in $K_1$ have first coordinate less then $x$] does not exceed the probability [for a random point in $K_2$ have first coordinate less then $x+c$]"? I probably should be able to prove such things, but alas, just now I feel myself disabled. $\endgroup$
    – Fedor Petrov
    Commented May 7, 2012 at 19:50
  • $\begingroup$ @Fedor: sorry, I was thinking of something else. $\endgroup$
    – alvarezpaiva
    Commented May 7, 2012 at 20:25

2 Answers 2

Reset to default
17
$\begingroup$

No, the distance can be as big as you want. Take two isosceles triangles with small bases, which "look" in the opposite directions.

alt text

For the updated question, the answer is still "NO". Again take long thin isosceles triangle with small base $\ll\varepsilon$. The distance between the barycentre of triangle and its $\varepsilon$-neigborhood is about $$\tfrac16{\cdot}\mathop{\rm diam}.$$

This is the upper bound for $\mathbb R^2$; for $\mathbb R^n$ you should get $$(\tfrac12-\tfrac1{n+1}){\cdot}\mathop{\rm diam}.$$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, indeed! So I change the question a bit, though probably the answer is again negative. $\endgroup$
    – Fedor Petrov
    Commented May 7, 2012 at 20:15
5
$\begingroup$
  1. This question has been first discussed in the paper [ABB] below. They show that, in the plane, the barycenter of the boundary has the desired property: It is Lipschitz-continuous with respect to the Hausdorff distance. (However, the Lipschitz constant is larger than 1.)
  2. Other such "reference points" which are Lipschitz-continuous w.r.t. the Hausdorff-distance, or w.r.t. some other metric (like the area of the symmetric difference) have been investigated. The objective is to get a fast heuristic or initial solution for matching two shapes under translation. A good starting point into the literature might be Oliver Klein's Ph.D. thesis "Shape Matching With Reference Points" from 2008.
  3. The best Lipschitz constant (for the Hausdorff distance) is achieved by the so-called Steiner point (or Steiner center). In functional analysis, such "reference points" are known under the name "continuous selectors". It has been proved (by non-constructive methods, however) that the Steiner point has the smallest possible Lipschitz constant w.r.t. the Hausdorff distance.
  4. One can show by an elementary example that a reference point (a mapping from compact convex sets to points that is equivariant under, say, isometries) cannot have Lipschitz-constant 1 in dimension 2 or larger. (Thus the answer to the first, strong, part of the original question is NO, even if you think of other points than the barycenter.)

[ABB] Helmut Alt, Bernd Behrends, Johannes Blömer. Approximate matching of polygonal shapes. Ann. Math. Artif. Intell., Volume 13, Pages 251-266, 1995, doi:10.1007/BF01530830. The conference version may be easier to access: Proceedings of the seventh annual symposium on computational geometry, pp.186-193, June 10-12, 1991, North Conway, New Hampshire. ACM Press. doi:10.1145/109648.109669.

Improve this answer
$\endgroup$
7
  • $\begingroup$ It is of course always hard to say which paper is the "first" reference on a given subject. The merits of [ABB] notwithstanding, they are hardly the first. For instance, Aubin & Cellina: "Differential inclusions", Springer, 1984 has this theorem as Theorem 1 in Chapter 1, Section 9: Let F be a bounded, Lipschitz map from a metric space to the compact convex subsets of $R^n$ (endowed with Hausdorff metric). Then $F$ has a Lipschitz selection $f$, i.e. $f(x) \in F(x)$ for all $x$. This is proved by showing that $f(x) = barycenter(F(x))$ is the desired selection. $\endgroup$
    – Fabian Wirth
    Commented Oct 12, 2022 at 14:32
  • $\begingroup$ @FabianWirth. This theorem has more general assumptions, but one can apply it to the current problem: E.g. take the metric space to be the set of compact nonempty convex subsets of $R^n$ itself (with Hausdorff metric), and let $F$ be the identity map. Nevertheless I am surprised by the claimed proof: The example of the triangles in the other answer shows clearly that the barycenter does not work. $\endgroup$
    – Günter Rote
    Commented Oct 13, 2022 at 20:25
  • $\begingroup$ It just shows that the Lipschitz constant is not $1$, doesn't it. $\endgroup$
    – Fabian Wirth
    Commented Oct 14, 2022 at 21:09
  • $\begingroup$ In the example of the triangles in the other answer, the Hausdorff distance is as small as you want (on the order of ϵ), while the distance between the barycenters of the two triangles can remain constant (1/3 of the horizontal extension (altitude) of the triangles if the triangles are vertically aligned). Thus, there can be no Lipschitz constant at all for this map. $\endgroup$
    – Günter Rote
    Commented Oct 16, 2022 at 11:04
  • $\begingroup$ You are correct. I have misquoted Aubin and Cellina. Apologies to you and to them as well. I read superficially, ts, ts. Indeed, for their selection they do not take the barycenter of F, but the barycenter of "F+unit ball". This then gives the Lipschitz selection. The barycenter itself is not even continuous, as the example above shows. $\endgroup$
    – Fabian Wirth
    Commented Oct 16, 2022 at 18:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .