<p>Given a bitmap image with some blots of solid color on it, what algorithm would you employ to construct polygons in the same shape as the blots?</p>

<p>This can be done in multiple steps: a high-resolution polygon could be later cut down by a best fit algorithm.  Bonus points if you can tell me how to cut the resulting polygons into convex components so that they can be rendered in OpenGL without problems.</p>

Reverse rasterizing is referred to as
vectorizing
.  The algorithms are generally quite complex, here's a
googlet
of a few of them.  Check out sparse pixel tracking and sparse pixel vectorization for some good examples.
For good algorithms for polygon partitioning, check out Joespeh O'Rourkes 'Computational Geometry in C', ISBN 0-521-44034-3, or search for
concave polygon partitioning
algorithms, such as
this