I want to understand the structure of a multiplicatively weighted voronoi diagram. I found that the bisector between 2 sites is circle shaped, but couldn't formally see it. can someone explain?
Thanks, Ohad.


About "multiplicatively weighted Voronoi diagrams" see here:


For the benefit of the readers I give a short description: You have a set of cities $p_i$ in the euclidean plane $E:={\mathbb R}^2$, and each of these cities has a given weight $w_i>0$. The "felt distance" $d(z,p_i)$ from an arbitrary point $z\in E$ to the city $p_i$ is defined to be $$d(z,p_i)\ :=\ {|z-p_i| \over w_i}\ ,$$ where $|z-z'|$ denotes the euclidean distance. This means that the "felt distance" to a city with large weight is comparatively small, and conversely, that the $d$-unit-disk of a city with large weight has a large euclidean radius.

Cosider now two cities $p$ and $p'$ with respective weights $w$ and $w'$. The $d$-Voronoi-boundary $\partial$ between these two cities consists of the points $z\in E$ which have the same $d$-distance to $p$ and to $p'$, i.e., it is defined by the equation $${|z-p|\over |z-p'|} \ =\ {w\over w'}\ .\qquad (*)$$ This says that $\partial$ is the locus of all points $z\in E$ for which the ratio $|z-p|/ |z-p'|$ has the a priori given value $\lambda:=w/w'$. It is a theorem of elementary geometry that such a locus is a circle, called the ${\it Apollonian\ circle}$ for the given data $p$, $p'$ and $\lambda$. The simplest proof is by choosing $p=(0,0)$, $p'=(c,0)$. Then the condition $(*)$ becomes $x^2+y^2=\lambda^2\bigl((x-c)^2 + y^2 \bigr)$, which can be simplified to the equation of a circle (or a line).

  • $\begingroup$ Belated "thanks" for that answer from another interested reader (me). I was googling for an answer to exactly that same question, and your explanation is the clearest I found (indeed, so clear that I'm now embarrassed to have needed to ask the question in the first place:). $\endgroup$ – John Forkosh Mar 5 '16 at 12:00

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.