Voronoi Diagrams and Application(s)

'Tis a sad sad time for me, Don Juan. I　had built my City of Love and all was going swimmingly. But then, I flew too close to the sun on wings of my libido. That is to say, I got greedy. I took on too many lovers and had to build too many houses in my City of Love. My "graph" of houses could not be "planar". There were many criss-crosses and intervening houses. Now they all think I'm a eighty-timing bastard when actually all Don Juan has is a big heart full of love, or as we say in my native Spain, mi corazón lleno de amor.

Anyways, now they're all after my blood. The bad news is I can't leave my City of Love because I work there. The good news is that my ladies never leave their houses due to a little "infestation" that I introduced to the city. Yes, yes, [that] was me. So what I want now is a way to navigate the City of Love such that I'm always as far away as possible from the houses of my ladies. Hey, apart from the office I still need to go buy groceries and other stuff. Fortunately, my Russian brother Georgy Voronoi and I sat down at the coffee shop the other day and worked out a neat solution. But the bastard named it after himself and left me for dead.



Here's a section of the City of Love with the houses demarcated using a Voronoi diagram:



As long as I stay on the black lines, I will be as far away from the surrounding houses as I possibly can, and hopefully out of firing range of the ladies.

Every black line is a bisecting line between two adjacent houses:



The Voronoi diagram is built up from the bisecting lines of adjacent point pairs:



And thus, the city of Paris was divided into the 80 districts of today.

The End

..................

Interesting Points of Interest - The owner of this blog has no affiliation whatsoever with Brother Juan.