4 deleted 20 characters in body

I do not have a definitive answer, but since you are looking for conditions as general as possible, I'd like to introduce some notions in general and give some hints, hoping somebody may add something, references included.

For $a:=(a_1,\dots,a_n)\in\mathbb{R}^n$ the set $R_i=R_i(a)$ is a sublevel set of the function $\varphi _ i^a(z):=\max _ j \big(f _ i(z) - f _ j(z) -a _ j\big)$. So the first step is understanding when a function $\varphi$ has all its sublevel sets connected. This has a reasonable answer for continuous function on a separable compact Hausdorff topological space, and a relevant notion is that of weakly isolated local minimum (warning: not standard; maybe somebody can suggest a better name).

Definition. A point $x\in X$ is a weakly isolated local minimum point for a function $\varphi:X\to\mathbb{R}$ if and only if it has a neighborhood $U$ (an isolating nbd) such that

• $\varphi(x)\le \varphi(y)$, for any $y\in U$
• $\varphi(x) < \varphi(y)$, for any $y\in \partial U$.

Thus for instance, any strict local minimum is a w.i.l.m. (any small nbd is isolating) and a global minimum as well ($U=X$ is an isolating nbd, for it has empty boundary); a monotone surjective function on $\mathbb{R}$ has no w.i.l.m. point, though it may certainly have local minimum points. If $\varphi$ is a continuous function on compact metric space and $x$ is a local minimum point at level $\varphi(x)=c$ and admits an isolating nbd $U$, then any other nbd $V\subset U$ of the compact set $U\cap\{ \varphi = c \}= \overline U\cap\{ \varphi = c \}$ is isolating as well.

Let's denote $M=M(\varphi)$ the set of weakly isolated local minimum points of the function $\varphi:X\to \mathbb{R}$. $\varphi$. The following holds assuming $\varphi$ continuous and $X$ a compact metric space (the proof seems OK; I will add details at request).

1. The set $\varphi(M)\subset\mathbb{R}$ is at most countable; thus $\varphi$ is constant on each component of $M$;

2. The connected component of any $x\in M$ in $M$ is closed; in fact, it coincides with the connected component of $x$ in its level set $\{\varphi=c\}$. The set $M$ is an $F_\sigma$ set.

3. All sublevel sets of $\varphi$ are connected if and only if $M$ is connected.

A further sep should be, understanding when two, or more continuous functions $\varphi_j$ on $X$ are such that $\max_j (\varphi_j+ a_j)$ has all sublevel sets connected for all $a_j\in\mathbb{R}$. Since $\{ \max _ j (\varphi _ j + a _ j) \le c\} = \cap _ j \{ \varphi_j\le c- a_ j\}$, this is the same as saying that all intersections of sublevel sets of $\varphi _ 1,\dots,\varphi _ n$ meet in connected sets. For two functions, by the above result, this is equivalent to: The sets $M ( {\varphi _ 1} _ { | \{ \varphi _ 2 \le c \} })$ are connected for all $c$. But it would be nice a further reduction, eliminating the quantification over all $c$. I do not see a simple equivalent form, but maybe there are reasonable sufficient conditions (possibly on the gradient of the functions, in a differentiable context).

3 added 5 characters in body

I do not have a definitive answer, but since you are looking for conditions as general as possible, I'd like to introduce some notions in general and give some hints, hoping somebody may add something, references included.

For $a:=(a_1,\dots,a_n)\in\mathbb{R}^n$ the set $R_i=R_i(a)$ is a sublevel set of the function $\varphi _ i^a(z):=\max _ j \big(f _ i(z) - f _ j(z) -a _ j\big)$. So the first step is understanding when a function $\varphi$ has all its sublevel sets connected. This has a reasonable answer for continuous function on a separable compact Hausdorff topological space, and a relevant notion is that of weakly isolated local minimum (warning: not standard; maybe somebody can suggest a better name).

Definition. A point $x\in X$ is a weakly isolated local minimum point for a function $\varphi:X\to\mathbb{R}$ if and only if it has a neighborhood $U$ (an isolating nbd) such that

• $\varphi(x)\le \varphi(y)$, for any $y\in U$
• $\varphi(x) < \varphi(y)$, for any $y\in \partial U$.

Thus for instance, any strict local minimum is a w.i.l.m. (any small nbd is isolating) and a global minimum as well ($U=X$ is an isolating nbd, for it has empty boundary); a monotone surjective function on $\mathbb{R}$ has no w.i.l.m. point, though it may certainly have local minimum points. If $\varphi$ is a continuous function on compact metric space and $x$ is a local minimum point at level $\varphi(x)=c$ and admits an isolating nbd $U$, then any other nbd $V\subset U$ of the compact set $U\cap\{ \varphi = c \}= \overline U\cap\{ \varphi = c \}$ is isolating as well.

Let's denote $M=M(\varphi)$ the set of weakly isolated local minimum points of the function $\varphi:X\to \mathbb{R}$. $\varphi$. The following holds assuming $\varphi$ continuous and $X$ a compact metric space (the proof seems OK; I will add details at request).

1. The set $\varphi(M)\subset\mathbb{R}$ is at most countable; thus $\varphi$ is constant on each component of $M$;

2. The connected component of any $x\in M$ in $M$ is closed; in fact, it coincides with the connected component of $x$ in its level set $\{\varphi=c\}$. The set $M$ is an $F_\sigma$ set.

3. All sublevel sets of $\varphi$ are connected if and only if $M$ is connected.

A further sep should be, understanding when two, or more continuous functions $\varphi_j$ on $X$ are such that $\max_j (\varphi_j+ a_j)$ has all sublevel sets connected for all $a_j\in\mathbb{R}$. Since $\{ \max _ j (\varphi _ j + a _ j) \le c\} = \cap _ j \{ \varphi_j\le c- a_ j\}$, this is the same as saying that all intersections of sublevel sets of $\varphi _ 1,\dots,\varphi _ n$ meet in connected sets. For two functions, by the above result, this is equivalent to: The sets $M ( {\varphi _ 1} _ { | \{ \varphi _ 2 \le c \} })$ are connected for all $c$. But it would be nice a further reduction, eliminating the quantification over all $c$. I do not see a simple equivalent form, but maybe there are reasonable sufficient conditions (possibly on the gradient of the functions, in a differentiable context).

2 edited body

I do not have a definitive answer, but since you are looking for conditions as general as possible, I'd like to introduce some notions in general and give some hints, hoping somebody may add something, references included.

For $a:=(a_1,\dots,a_n)\in\mathbb{R}^n$ the set $R_i=R_i(a)$ is a sublevel set of the function $\varphi _ i^a(z):=\max _ j \big(f _ i(z) - f _ j(z) -a _ j\big)$. So the first step is to understand understanding when a function $\varphi$ has all its sublevel sets connected. This has a reasonable answer for continuous function on a separable compact Hausdorff topological space, and a relevant notion is that of weakly isolated local minimum (warning: not standard; maybe somebody can suggest a better name).

Definition. A point $x\in X$ is a weakly isolated local minimum point for a function $\varphi:X\to\mathbb{R}$ if and only if it has a neighborhood $U$ (an isolating nbd) such that

• $\varphi(x)\le \varphi(y)$, for any $y\in U$
• $\varphi(x) < \varphi(y)$, for any $y\in \partial U$.

Thus for instance, any strict local minimum is a w.i.l.m. (any small nbd is isolating) and a global minimum as well ($U=X$ is an isolating nbd, for it has empty boundary); a monotone surjective function on $\mathbb{R}$ has no w.i.l.m. point, though it may certainly have local minimum points. If $\varphi$ is a continuous function on compact metric space and $x$ is a local minimum point at level $\varphi(x)=c$ and admits an isolating nbd $U$, then any other nbd $V\subset U$ of the compact set $U\cap\{ \varphi = c \}= \overline U\cap\{ \varphi = c \}$ is isolating as well.

Let's denote $M=M(\varphi)$ the set of weakly isolated local minimum points of the function $\varphi:X\to \mathbb{R}$. $\varphi$. The following holds assuming $\varphi$ continuous and $X$ a compact metric space (the proof seems OK; I will add details at request).

1. The set $\varphi(M)\subset\mathbb{R}$ is at most countable; thus $\varphi$ is constant on each component of $M$;

2. The connected component of any $x\in M$ in $M$ is closed; in fact, it coincides with the connected component of $x$ in its level set $\{\varphi=c\}$. The set $M$ is an $F_\sigma$ set.

3. All sublevel sets of $\varphi$ are connected if and only if $M$ is connected.

A further sep should be, to understand understanding when two, or more continuous functions $\varphi_j$ on $X$ are such that $\max_j (\varphi_j+ a_j)$ has all sublevel connected for all $a_j\in\mathbb{R}$. Since $\{ \max _ j (\varphi _ j + a _ j) \le c\} = \cap _ j \{ \varphi_j\le c- a_ j\}$, this is the same as saying that all intersections of sublevel sets of $\varphi _ 1,\dots,\varphi _ n$ meet in connected sets. For two functions, by the above result, this is equivalent to: The sets $M ( {\varphi _ 1} _ { | \{ \varphi _ 2 \le c \} })$ are connected for all $c$. But it would be nice a further reduction, eliminating the quantification over all $c$. I do not see a simple equivalent form, but maybe there are reasonable sufficient conditions (possibly on the gradient of the functions, in a differentiable context).

1