2
$\begingroup$

Let $C$ be a (nonempty) compact subset of euclidean $\mathbb R^n$, and consider the set-valued map $p_C:\mathbb R^n \to 2^C$ defined by $$ p_C(x) = \{c \in C \mid \|x-c\| = \mbox{dist}(x,C)\}, $$ where $\mbox{dist}(x,C) := \inf_{c \in C}\|x-c\|$ is the distance of $x$ from $C$.

Question. Under what minimal conditions on $C$ is $p_C$ Lipschitz-continuous w.r.t Hausdorff distance ?

Note. The case where $C$ is closed and convex is fully solved. Indeed, in such a case, $p_C$ is single-valued and non-expansive (and therefore $1$-Lipschitz).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ To break Lipschitz, just take any curve that passes through an isolated point $p$ at which $|p_C(p)|>1$. For example, you can use my answer [mathoverflow.net/a/412698/29873] to your previous question to construct a curve along which $p_C$ is constantly $\{x\}$, and then $\{x,y\}$ at $p$, and then constantly $\{y\}$. The Hausdorff distance between $\{x\}$ and $\{y\}$ is just $\|x-y\|$, which is fixed, but the corresponding points on the curve can be arbitrarily close on opposite sides of $p$. $\endgroup$
    – Dustin G. Mixon
    Commented Dec 29, 2021 at 13:43
  • $\begingroup$ This makes sense, thanks. $\endgroup$
    – dohmatob
    Commented Dec 29, 2021 at 14:16

1 Answer 1

Reset to default
1
$\begingroup$

Seems like in fact convex sets are the only ones for which $p_C$ is continuous. To prove this, we can begin by noticing that for a set $C$ with the property, $p_C$ can only take one point sets as values. If not, let $x,a_1,a_2$ be different points with $a_1,a_2\in p_C(x)$. Then any point $y$ in the open segment from $x$ to $a_i$ has $p_C(y)=\{a_i\}$, so $p_C$ cannot be continuous at $x$.

So, if for a compact $C$, $p_C$ is continuous, then it is single valued. So this shows that $C$ has to be convex.

Edit: From Dustin G. Mixon's comment above, it seems like the nearest point mapping is well studied. A reference that if a compact set $C$ is not convex, then the nearest point mapping is not single valued would be welcome.

Improve this answer
$\endgroup$
3
  • $\begingroup$ For reference, consider Gromov's "Sign and Geometric Meaning of Curvature", pp. 16, especially "when $\epsilon$ becomes equal to $-\lambda_i^{-1}(0) \ldots"$. Whenever the principle curvatures are negative with respect to the exterior, then there will be nonunique argmins at a sufficiently far distance. Another reference is the fact that Blum's medial axis $M(A)$ of an open set $A$ is nonempty, not to mention homotopy-equivalent to $A$. $\endgroup$
    – JHM
    Commented Dec 30, 2021 at 20:14
  • $\begingroup$ In the language of the following link, Motzkin's Theorem gives that every Chebyshev subset of $\mathbb{R}^n$ is a nonempty closed convex set: web.archive.org/web/20120312180417/https://files.nyu.edu/eo1/… $\endgroup$
    – Dustin G. Mixon
    Commented Dec 30, 2021 at 21:56
  • $\begingroup$ Thanks to both! $\endgroup$
    – Saúl RM
    Commented Dec 30, 2021 at 22:14

You must log in to answer this question.

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