The Voronoi diagram is a well-known data structure that helps solve various proximity problems. We have several nice algorithms that build this diagram for $n$ point in optimal time $O(n\log n)$.
I am interested to solve this problem for a set of simple, disjoint polygons and I am collecting information about known solutions. Actually, what matters to me is to know for every polygon which other polygon shares an edge of the diagram with it, which is a quasi-equivalent problem (I mean that the graph structure is enough, I don't need the exact geometry).
I have heard of the compact Voronoi diagrams and the are certainly an option. I am also interested in the Voronoi diagram of the convex hulls of these polygons, which might be easier to construct, but in this case it is no more guaranteed that they are disjoint.
My polygons have a few dozens vertices and there are a few dozens of them. Approximate solutions are allowed. Speed and ease of implementation are more important.
I would welcome any information about these problems and their algorithmic resolution.