| Weight of added points: | Randomize weights of new points:

Draw Delaunay triangulation, extra hyperbolas, intersection points:

Click to place sites with weight specified by text box, starting from one of 7 test cases (test case 0 is empty). The additively weighted Voronoi diagram (or Apollonius graph) is calculated, which is a modification of the regular Voronoi diagram in which the curves dividing regions are equidistant from disks in the corresponding regions rather than sites. The weight of a site equals the radius of its disk. This leads to segments of hyperbolas between sites instead of straight lines.

My algorithm is buggy and fails for diagrams with more than a few points. The CGAL link above has a working implementation that is more efficient as well. My implementation is brute-force, taking the following steps for each site added:

- Remove any sites with a weight that is too low -- less than the weight of another site minus the distance to that site -- these are colored blue
- Find all points equidistant from any triplet of disks corresponding to weighted sites
- For sites
*i,j,k*, this is done by finding the intersection of the hyperbolic segment between*i*and*j*and the segment between*i*and*k* - Finding this intersection requires solving a quartic (4th order) polynomial equation
- Sort sites by weight (descending order) and loop through all sites
*i*having intersection points calculated above - Sort intersection points by angle, and pick the closest one
*p* - Note that each intersection point is a junction of 3 hyperbolic segments between sites, so for site
*i*, the intersection point has clockwise and counterclockwise neighbor sites corresponding to segments equidistant from*i*and the respective sites - Iterate through other intersections in clockwise order, finding the next intersection that has the clockwise neighbor site of
*p*as a counterclockwise neighbor (so we know they are connected) - Do the same in the counterclockwise direction, and combine the two lists, keeping track of intersection points and neighbors (being careful about the possibility of complete loops as well)
- Draw the hyperbola segments by using intersection points as lower and upper bounds (in rotated coordinate system)
- Note: a given site can have multiple disjoint connected sets of neighbor sites