# Prove that Voronoi cells are path-connected

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!

## 1 Answer

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.