Voronoi diagram algorithm with non-euclidean metric

Do you know any easy to implement algorithm for constructing a Voronoi diagram from a given set of points on a surface, using some different metric (taxicab, for instance)?
It can be some modification of Fortune's algorithm.

It depends on the metric and your sites. There is a framework called abstract Voronoi diagram that allows you to compute Voronoi diagrams for well-behaved instances. In order to define what well-behaved means you have to give certain guarantees for the bisecting curves defined by your sites and your metric (for example two such curves intersect only in a finite number of points). The exact requirements might differ slightly depending on the paper you read.

If your problem is a abstract Voronoi diagram, then you can compute it with (a variant) of the randomized incremental construction due to Clarkson and Shor - see for example here. Then everything boils down to computations with the bisecting curves.

Note that there is quite some literature about these Voronoi diagrams and also recent progress has been made. I would advice you to go through this.

StackExchange Computer Science Q#34116, answer score: 4