| 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
This runs into problems with isolated sites that may only have one hyperbola segment in the diagram because of a large-weight neighbor, but because of intersections with other small-weight sites, extraneous segments are drawn (and the single desired segment is not -- test case 4 shows an example of this).