Split a cell in voronoi diagram

Question

My work involves using voronoi diagrams, and my next task is to split a cell inside this diagram in half(aprox.)

More accurately: I have a set of (x,y) points, I am using a library which takes care of drawing this diagram, and I have to find a new (x,y) point (or two, I am not really sure), insert it into that set, redraw it, so that the original cell is divided in half.

My idea was that I should use the average coordinates of the neighbors and insert that new point, but this works only with cells in the center of the diagram. Those cells which are close to the edge of the box remain quite big after splitting it with this strategy.

I assume that this is a geometry problem, and any help would be appreciated.

I have attached two images, the first one is the initial diagram, and in the second one you can see how all cells have been split using the average strategy. It's obvious that the splitting is not working as I want it to.

Before image After image

Answer 1

In order to reduce border effects, imagine you are working on a cylinder, or better said on a torus; this will be realized by replicating the set of points on each ide of the original square or rectangle as shown on the figure below where you can see that the exceptional cells have no influence on the cells of the central square, the only square that will be kept.

Answer 2

Just replace the original point with two points very close together. The split will bisect the line joining them.

What "very close together" means will depend on the original spacing of the other points. Much closer than the smallest original spacing is what is required.