| 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:

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).

Home