Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

About "multiplicatively weighted Voronoi diagrams" see here:

http://www.nirarebakun.com/voro/emwvoro.html

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).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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