Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XLI-B2, 109-114, 2016
http://www.int-arch-photogramm-remote-sens-spatial-inf-sci.net/XLI-B2/109/2016/
doi:10.5194/isprs-archives-XLI-B2-109-2016
 
07 Jun 2016
BEYOND MAXIMUM INDEPENDENT SET: AN EXTENDED MODEL FOR POINT-FEATURE LABEL PLACEMENT
Jan-Henrik Haunert1 and Alexander Wolff2 1Geoinformatics Group, Institut für Informatik, Universität Osnabrück, Germany
2Lehrstuhl für Informatik I, Universität Würzburg, Germany
Keywords: Map labeling, point-feature label placement, NP-hard, integer linear programming, cartographic requirements Abstract. Map labeling is a classical problem of cartography that has frequently been approached by combinatorial optimization. Given a set of features in the map and for each feature a set of label candidates, a common problem is to select an independent set of labels (that is, a labeling without label–label overlaps) that contains as many labels as possible and at most one label for each feature. To obtain solutions of high cartographic quality, the labels can be weighted and one can maximize the total weight (rather than the number) of the selected labels. We argue, however, that when maximizing the weight of the labeling, interdependences between labels are insufficiently addressed. Furthermore, in a maximum-weight labeling, the labels tend to be densely packed and thus the map background can be occluded too much. We propose extensions of an existing model to overcome these limitations. Since even without our extensions the problem is NP-hard, we cannot hope for an efficient exact algorithm for the problem. Therefore, we present a formalization of our model as an integer linear program (ILP). This allows us to compute optimal solutions in reasonable time, which we demonstrate for randomly generated instances.
Conference paper (PDF, 788 KB)


Citation: Haunert, J.-H. and Wolff, A.: BEYOND MAXIMUM INDEPENDENT SET: AN EXTENDED MODEL FOR POINT-FEATURE LABEL PLACEMENT, Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., XLI-B2, 109-114, doi:10.5194/isprs-archives-XLI-B2-109-2016, 2016.

BibTeX EndNote Reference Manager XML