This sounds like a good situation to use Signed Distance Fields. It's often used for text rendering to achieve high quality and sharp results when zooming (and rotating), but it can also be used for any black & white images. See this video and the image below.
Typically when text is prerasterized to bitmaps, each pixel stores the alpha value. 0 means transparent, 1 means opaque and values between are semitransparent due to antialiasing the edges. With signed distance fields the idea is to create a bitmap where each pixel stores the distance to the nearest edge. Values < 0 are outside the shape and values > 0 are inside the shape. When rendering, this information is read from the bitmap and the alpha value is decided on runtime based on the distance and "spread". Spread here means how sharp you want the edge to be, usually chosen so that the resulting antialiased edge is no wider than 1 pixel on the screen.
The nice thing about distance fields is that when zoomed in, the distances to straight edges stay accurate when the bitmap is sampled with bilinear filtering. This allows arbitrary zooming without pixelating or blurring. You just need to provide the spread matching the zoom level. This technique is also very fast to render, as it only requires a custom shader with a single texture lookup + some simple math. This is going to be a lot faster than polygon based methods. Distance fields also allows some effects easily, mainly borders around or inside the shapes: [freetype-gl] Example image with effects http://freetype-gl.googlecode.com/svn/wiki/images/cartoon.png
The generation of the distance field can be a problem, as it's not trivial to calculate it from arbitrary shapes. Fortunately for you it should be pretty straigthforward, as you already seem have the distance information available as you are generating a voronoi diagram.
An additional bonus from distance fields is that it can be very friendly for some physics or lighting calculations. As an example PixelJunk Shooter used it for collisions.
The only problem I can see for your case seems to be that your map is not black and white. From the description it's not clear what the different shades of gray indicate. You could just sample the colors from traditional bitmaps or have multiple distance fields, one for each color. Or you could invent something totally different, but it all depends what you want to do.