Let we have a similarity function $d: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$. It can be a metric, but not necessarily it. We introduce the natural generalization of Voronoi cells in terms of this similarity function. Let we have a finite set of $n$-dimensional vectors $X$. We call the Voronoi cell $R_k$ associated with the element $x_k \in X$ the following set $$ R_k = \{x \in \mathbb{R}^n| d(x, x_k) < d(x, x_j)~\forall j\ne k \}$$
My question is: what property we have to require from $d(x,y)$ for all Voronoi cells be path-connected for all possible finite sets $X$? My conjecture is that this is in some way related to convexity $d(x,y)$.
I can prove path-connectedness in some particular cases of $d(x,y)$. For example, if $d(x,y) = \|x-y\|_2$ then the border between two points is linear, so every Voronoi cells is a polyhedron is this case.
Another easy case is linear functions. In this case let $u$ and $v$ be arbitrary points from one Voronoi cell $R_x$ for $x \in X$. So $d(x, u) < d(w, u)$ and $d(x, v) < d(w, v)$ for $\forall w \ne x$. Hence $$ d(x, tu + (1-t)v) < d(w, tu + (1-t)v),~t\in[0,1] $$ So the Voronoi cell is convex.
It would be wonderful to find a necessary and sufficient condition for the path-connectedness of Voronoi cells, but it is enough for me to simply have a richer class of functions than the ones I have.
Great thanks for any advices, ideas, papers and so on!
Assume that $d(x,y)=f(|x-y|)$ where $f:\mathbb{R}_+\rightarrow \mathbb{R}_+$ and $f(0)=0,\ f(x)>0$ for $x>0$.
Show that connected implies that $f$ is increasing, when $n=1$.
Proof : Assume that $$ 0<x_1<x_2<x_3 $$
$$ f(x_1)>f(x_2)< f(x_3) $$
Then $p=0,\ q=x_1+x_2$ so that Voronoi domain for $q$ is not connected.