* the diagram is open on it's edges
I'm not sure what you mean. :?

* the center of each region need tobe calculated before (so that there's no acute angle)
I guess you can just pass a big array of points to the algorithm, without any extensive pre-processing. I can imagine you want to check the distances between the points and delete the close ones, so that the points are nicely distributed over the area.

Unfortunatly, i cant help you with the actual implementation. I think fortune's algo can be implemented without a lot of problems. You have to check if it's suitable for your purposes and if it can deliver the information you want.