Planar Voronoi on non-planar surface

Hello everyone,

I can't be the first one to ask this question, but I really didn't find anything related to the problem I am having:

I'm currently working with possible arrangements of plate structures. In short, planar surfaces.

So, I'm looking for a method for applying planar voronoi cells to a non-planar (e.g. hyperbolic) surface. Using the Pointset-Reconstruction Tools from McNeel does project the cell's corner points on a surface and connects them, but the voronoi cells themselves aren't planar.

By playing around with hexagons I figured out that putting planar vornoi cells on a non-planar surface you would end up with some angles facing inwards (like a C-shaped voronoi cell)

Any ideas how to do this?

Putting planes in each cell center and intersecting them with each other is kinda complicated and led to strange solutions so far...