Let $E$ be a subset of $\mathbb{R}^n$ such that $\mathbb{R}^n \setminus E$ is convex.
Let $x,y$ be in $\mathbb{R}^n$. Is it true that for $t\in [0,1]$, we have: $$d(tx+(1-t)y,E) \geq td(x,E) - (1-t)d(y,\mathbb{R}^n \setminus E)?$$ If yes, do you know why?
Let $F=\mathbb R^n\setminus E$. The inequality $d(x,E)\geq a$ means that the open ball $B_a(x)$ does not intersect $E$, i.e., that $B_a(x)\subseteq F$. Now, if $a=d(x,E)$ and $b=d(y,E)$, then $B_a(x),B_b(y)\subseteq F$, thus by the convexity $B_{ta+(1-t)b}(tx+(1-t)y)=tB_a(x)+(1-t)B_b(y)\subseteq F$, which means exactly what you want.
I think this is true, and it should have an elementary (if tedious) proof. I'll discuss the easiest case explicitly; I believe the others could be dealt with in the same way, but I haven't worked out the details and will leave this to the proverbial "reader."
First of all, by translation invariance, we can assume that $x=0$; I also want to relabel $s=1-t$. We then want to show that $$ d(sy,E) \ge (1-s)d(0,E)-sd(y,E^c) . $$ This is trivial if $0\in E$, so we can assume that $0\notin E$ and are then left with the cases: (1) $y\notin E$; (2) $y\in E$, which splits into the subcases (a) $sy\in E$, (b) $sy\notin E$.
In case (1) the claim becomes $d(sy,E)\ge (1-s)d(0,E)$. This holds because $d(0,E)$ is the radius of the largest ball about $0$ whose interior is contained in $E^c$, and if we now take the convex hull of this ball and $y\in E^c$ then we see that $E^c$ contains a rescaled ball about $sy$ that gives the desired inequality (clearest from a picture).
This procedure (translate the distances into balls that are contained in $E^c$ and fool around with those by taking convex hulls) should work in all cases. The ugliest case is (2)(b) because now the inequality has three terms. I suggest to proceed as follows: interpret $d(0,E)$ as above (existence of a ball about $0$ that is contained in $E^c$). Then parse $d(y,E^c)$ as "there's a point of $E^c$ within that distance of $y$," and then take the convex hull of this point and the ball from the previous step. If $d(y,E^c)$ is small, this will show that $E^c$ contains a ball of a certain radius about $sy$ (thus bounding $d(sy,E)$ from below, as desired). If $d(y,E^c)$ is large, the RHS becomes negative and we're not claiming anything. Let's just hope this gives the bound as claimed in this case also.
