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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.