Chez Chesler

According to my Computational Geometry in C textbook (by Joseph O'Rourke) the Voronoi diagram is a geometric structure second in importance only to the convex hull. He continues with some applications:

Imagine a vast forest containing a number of fire observation towers. Each ranger is responsible for extinguishing any fire closer to her tower than to any other tower. The set of all trees for which a particular ranger is responsible constitutes the "Voronoi polygon" associated with her tower. The Vornoi diagram maps out the lines between these areas of responsibility: the spots in the forest that are equidistant from two or more towers.

Imagine now the perverse situation where all the rangers ignite their towers simultaneously, and the forest burns at a uniform rate. The fire will spread in circles centered on each tower. The points at which the fire quenches because it reaches previously consumed trees are those points equidistant from two or more towers, which are exactly the points on the Voronoi diagram.

My city is redistricting its 9 elementary schools. Voronoi diagrams come to mind, to suggest a districting such that each child attends the nearest school. And I'm trying to use one of the algorithms O'Rourke discusses to make the diagram for the city. But even if I do, there are at least five wrinkes:

• The schools have different capacities
• The population density, especially the population of school-age children, is not uniform
• Pythagorean distance is not as important as over-the-road distance. For instance, a cul-de-sac may empty onto a street in the opposite direction from the houses on that cul-de-sac than a school: the effective distance to that school is not the straight-line distance from the house to the school, but the distance from the house to the intersection of the cul-de-sac with the street, and from there, over roads, to the school.
• Some schools are more desirable than other schools. I suppose the diagram is to help form a fair and equitable districting, but a school which is more desirable will have a greater "yield" -- more eligible students will attend it -- than a less desirable school, so its district should be smaller.
• Some clusters of residences are so far from the nearest school that children who live there have to take a bus no matter what. In such a case, and especially if (for instance by virtue of being a new development) the residents have less claim on a particular near school, it may make sense to run a bus from that cluster to a further school. How do we account for this? The full bus going directly from a residence cluster to a school should have a cost function less than a bus making pickups along that route.

Any thoughts or solutions welcome.