Driven by the industrial challenge of labeling maps for GIS applications, we investigate the problem of computing the largest convex partitioning of the map
such that the rectangular axis-parallel label
can be placed in it. The map region to be labeled is in general non-convex and may contain holes. Our main result is the new polygonal area removal (PAR) algorithm to identify the area within
where the center of the label
can be placed. We then derive a new and faster algorithm based on the sweep technique that determines the complete set of maximum inscribed rectangles (MIR) in
in the most common case when rectangle sides have an axis-parallel orientation. The set of all maximum inscribed rectangles is then post-processed to produce the best size/orientation combination of the final label placement depending on the specific requirements from the end users.