Geometric and thematic integration of spatial data into maps

The map construction problem (MCP) is defined as a spatial data integration problem relating to the integration of region data into map data. Although a purely geometric integration of regions into a map is known and is efficient, algorithms preserving thematic data of regions are much more difficult. A naive approach to the MCP runs in O((nm lg nm)² + k) time for m regions composed with n line segments on average with k line segment intersections. A new O((n+k)(lg n+m+lg m²)) algorithm is presented to solve the MCP. The algorithm has been implemented and experiments show that it is significantly faster than the naive approach.