How to find Voronoi diagram with specific distance function?

1
votes

There are quite many algoritms for finding Voronoi diagram with Euclidean distance. However, I haven't found any algorithms other distance functions, for example, Manhattan distance (perhaps, because of no practical applications).

You can see example at Wikipedia:
https://en.wikipedia.org/wiki/Voronoi_diagram#/media/File:Manhattan_Voronoi_Diagram.svg

Manhattan Voronoi diagram also consists of polygons (but non-convex), so I guess that algorithm similar to Fortune's algorithm can be constructed. However, using more complex distance functions, boundaries won't be polygons anymore. There will be need in different data structure and algorithm.

Are there any algorithms for finding Voronoi diagram with specific distance function (in 2D for simplicity)?

Note: I don't need an algorithm which works with pixels, it's pretty straightforward, I need algorithm, which founds the boundaries of cells.

Note 2 Practically I need Voronoi diagram with distance function abs(dx)^3 + abs(dy)^3, however, theoretically, I'm interested how one do make an algorithm for other distance functions. Here is how Voronoi with abs(dx)^3 + abs(dy)^3 look like. Sites are continous and their edges resemble graphs of y=x^3 (just assumption).

Cubic distance

1
algorithmdistancevoronoi
github.com/bobbysoon/TaxiVoronoi – Micromega
If you are only interested in the algorithm (no code involved) this might be a good question for the Computer Science SE. There are a couple of questions I found here and here but unfortunately they don't have algorithms. – user812786
@whrrgarbl I'm more interested in algorithm, code will be too big to post on SO. I want to code it myself, if it's possible. – Somnium
The cubic distances are a mess. Try plotting a two-point diagram. – David Eisenstat
@DavidEisenstat No, they are pretty much normal. Added an image. – Somnium

1 Answers

0
votes

Most likely you can use the pixel taxi voronoi and give each polygon a different color. You can then use a pixel color test to check the bounds.