Is it possible to construct a medial axis for a complex, non-convex polygon with holes in sub-quadratic time? Could you point me to the algorithm explanation?
Or maybe there is a library for it in Java?
http://en.wikipedia.org/wiki/Medial_axis hints at a Voronoi diagram link, and IIRC Voronoi diagrams can be calculated in n log n time (Fortunes algorithm).
I think there's still some work to do afterwards, though - selecting edges (and perhaps partial edges) from that Voronoi diagram. Basically, the Voronoi diagram is based on the vertices in the polygon and lacks the information about the edges, and about which regions are filled and which are holes. So there must be something left to do to take that extra information into account.
However, once you have the Voronoi diagram, hopefully this extra work can be done in linear time. The Voronoi diagram itself gives an index structure you can use, e.g., for determining which edges of the polygon pass through which Voronoi cells.
I haven't thought this through properly, but one idea is that by clipping the Voronoi diagram to the original polygon, you may get the correct result.