I didn't quite get what you need the stencil buffer for in that technique.
(Plus, it was traditional to combine 24-bit depth with 8-bit stencil in the same buffer, so stencil writes were basically free if you're writing depth anyway.)
But what advantage does a two pass stencil technique have over just writing to the color buffer in the first pass?
But you're right, it doesn't sound massively compelling. And the traditional 24depth+8stencil buffer format would limit you to a maximum of 256 regions, which could easily cramp your style.
the complexity is num pixels*num entities.
implementation here: https://github.com/nraynaud/webgcode/blob/gh-pages/webapp/sh...
I would gladly show the result here: http://nraynaud.github.io/webgcode/various_tests/test_vorono... but it looks like Chrome removed PathSegList that the SVG library was using internally
edit: it still works in firefox, it extracts the voronoi diagram, the medial axis, then does a subtraction on the medial axis (internal offset of the original polygon), then a minimum threshold (mickey ears for pocketting in milling), then a reconstruction of the polygon from the altered medial axis.
The depth testing will only leave fragments of the cone that the corresponding pixel is closest to. If you need better precision, draw the "cone" by making a full screen quad and use the fragment shader to set depth (gl_FragDepth) according to distance from seed point (or just use enough vertices in the cones).
If you change the circular cone to a rectangular-based pyramid shape, you'll get Voronoi-type diagrams but with a different metric (manhattan distance?). Turn the rectangle 45 degrees to make a diamond shaped base and you have yet another metric.