I want to write software that merges groups of (mainly) adjacent polygons. For example, merge the US counties into sales regions. Then, display either the boundary of these sales regions or fill them with some color indicating let's say sales numbers.

Preprocessing and merging the given shapes in a GIS editor is not an option, the sales groups are not given in advance.

The GIS component I use has a function for merging polygons, but it is awfully slow. Reducing the number of vertices didn't help much. Neither having the common segments of the polygons use the exact same vertices.
But given the fact that the line segments of the polygons are duplicated in a shapefile (which I use at the moment as data source), I can imagine that the algorithm might have a lot of work to do.

So my question is, are there algorithms and/or data structures that can handle this problem efficiently?

I thought of maybe using Geo Markup Language which has the ability to define segments which can be referenced to make up polygons.