Minimum point-overlap labelling*. (4th May 2021)

• Record Type: Journal Article
• Authors: Higashikawa, Yuya; Imai, Keiko; Shiraga, Takeharu; Sukegawa, Noriyoshi; Yokosuka, Yusuke
• Is Part Of: Optimization methods and software. Volume 36:Number 2/3(2021)
• Page Start: 316
• Page End: 325
• Publication Date: 2021-05-04
• Subjects: Map labelling -- air-traffic control -- approximation algorithms; 68U05 -- 68W25; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1833880
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : In an application of map labelling to air-traffic control, labels should be placed with as few overlaps as possible since labels include important information about airplanes. Motivated by this application, de Berg and Gerrits (Comput. Geom. 2012) proposed a problem of maximizing the number of free labels (i.e. labels not intersecting with any other label) and developed approximation algorithms for their problem under various label-placement models. In this paper, we propose an alternative problem of minimizing a degree of overlap at a point. Specifically, the objective of this problem is to minimize the maximum of λ ( p ) over p ∈ R 2, where λ ( p ) is defined as the sum of weights of labels that overlap with a point p . We develop a 4-approximation algorithm by LP-rounding under the 4-position model. We also investigate the case when labels are rectangles with bounded height/length ratios.