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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
    
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:). – John Forkosh Mar 5 at 12:00

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.