Labeling circular focus regions based on a tractable case of maximum weight independent set of rectangles

Abstract

We introduce a new model for labeling point features in a circular focus region that a user can define in a map. In this model, each label is an axis-aligned rectangle that touches the boundary of the focus region with one of its corners. A straight-line segment (the leader of the label) connects that corner with the corresponding point feature to ensure a clear graphical association. We require that every leader points towards the center of the focus region, which improves legibility and, in particular, avoids intersecting leaders. Our model allows only one possible position for each label. Consequently, but also more generally due to limited map space, labeling all points without overlapping labels can easily become impossible. Therefore, we compute a conflictfree labeling with the maximal number of labels or with the maximal total weight, where the weight of each label corresponds to the importance of its corresponding point. Our problems are special cases of the NP-hard problem Maximum Weight Independent Set of Rectangles (MWISR). We show that MWISR can be solved efficiently if the upperleft corners of all rectangles (of potentially different heights) lie on a monotonically ascending curve. This allows us to compute optimal labelings efficiently, e.g., in O(n log n) time for unit-height labels. We achieve a real-time performance with an implementation in JavaScript that runs in a browser.