It's easy to freehand a Voronoi diagram if you can hold the Delaunay triangulation in your head.

Solving a Voronoi using origami requires only one type of fold, and skips the Delaunay triangulation.

Also using origami another delightful symmetry emerges:

Simultaneously creasing the three lines of a Voronoi intersection draws the three points to meet each other in space. Collapsing the Voronoi intersection flat will put a crease through each of the 3 points.

A. Add a line that runs parallel to a Voronoi wall segment but inset toward the point by a certain amount to your choosing.

B. Establish the endpoints at both the intersections to each edge crease.

repeat 

Between neighboring cells, lines are copies of themselves reflected across the shared cell wall.

It has this property: 

Each new boundary is same ratio distance between the point and the edge, along its perpendicular.

It also has this property:

Each smaller cell is an affine scale of its parent Voronoi cell with its homothetic center at the cell's point.

There are numerous ways to make the 3D back face lie flat. Squashing a triangle into an intersection gives equal president in Z-space to the 3 panels from the front perspective.

Triangles will most likely overlap too, it gets more complicated, but you can remedy them in a number of different ways.

Upper left: 4-way squash

Just to its right: 4-way fold over. no squash.

Center: squash, then fold over.

Bottom center: 2 triangles overlapping. squash together then fold to the side.