Mixed Map Labeling

Maarten Löffler; Martin Nöllenburg; Frank Staals

doi:10.1007/978-3-319-18173-8_25

Mixed Map Labeling

Maarten Löffler, Martin Nöllenburg, Frank Staals^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

Point feature map labeling is a geometric problem, in which a set of input points must be labeled with a set of disjoint rectangles (the bounding boxes of the label texts). Typically, labeling models either use internal labels, which must touch their feature point, or external (boundary) labels, which are placed on one of the four sides of the input points’ bounding box and which are connected to their feature points by crossing-free leader lines. In this paper we study polynomial-time algorithms for maximizing the number of internal labels in a mixed labeling model that combines internal and external labels. The model requires that all leaders are parallel to a given orientation θ∈[0,2π)
, whose value influences the geometric properties and hence the running times of our algorithms.

Original language	English
Title of host publication	Algorithms and Complexity
Subtitle of host publication	9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings
Editors	Vangelis Th. Paschos, Peter Widmayer
Publisher	Springer
Pages	339–351
Edition	1
ISBN (Electronic)	978-3-319-18173-8
ISBN (Print)	978-3-319-18172-1
DOIs	https://doi.org/10.1007/978-3-319-18173-8_25
Publication status	Published - 22 Apr 2015

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	9079
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Keywords

CG, GD, GIS

Access to Document

10.1007/978-3-319-18173-8_25

978-3-319-18173-8_25Final published version, 249 KBLicence: Taverne

Cite this

@inproceedings{da569ac439394874815a9293b780cf0b,

title = "Mixed Map Labeling",

abstract = "Point feature map labeling is a geometric problem, in which a set of input points must be labeled with a set of disjoint rectangles (the bounding boxes of the label texts). Typically, labeling models either use internal labels, which must touch their feature point, or external (boundary) labels, which are placed on one of the four sides of the input points{\textquoteright} bounding box and which are connected to their feature points by crossing-free leader lines. In this paper we study polynomial-time algorithms for maximizing the number of internal labels in a mixed labeling model that combines internal and external labels. The model requires that all leaders are parallel to a given orientation θ∈[0,2π), whose value influences the geometric properties and hence the running times of our algorithms.",

keywords = "CG, GD, GIS",

author = "Maarten L{\"o}ffler and Martin N{\"o}llenburg and Frank Staals",

year = "2015",

month = apr,

day = "22",

doi = "10.1007/978-3-319-18173-8_25",

language = "English",

isbn = "978-3-319-18172-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "339–351",

editor = "Paschos, {Vangelis Th. } and Widmayer, {Peter }",

booktitle = "Algorithms and Complexity",

edition = "1",

}

Mixed Map Labeling. / Löffler, Maarten; Nöllenburg, Martin; Staals, Frank.
Algorithms and Complexity: 9th International Conference, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings. ed. / Vangelis Th. Paschos; Peter Widmayer. 1. ed. Springer, 2015. p. 339–351 (Lecture Notes in Computer Science; Vol. 9079).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Mixed Map Labeling

AU - Löffler, Maarten

AU - Nöllenburg, Martin

AU - Staals, Frank

PY - 2015/4/22

Y1 - 2015/4/22

N2 - Point feature map labeling is a geometric problem, in which a set of input points must be labeled with a set of disjoint rectangles (the bounding boxes of the label texts). Typically, labeling models either use internal labels, which must touch their feature point, or external (boundary) labels, which are placed on one of the four sides of the input points’ bounding box and which are connected to their feature points by crossing-free leader lines. In this paper we study polynomial-time algorithms for maximizing the number of internal labels in a mixed labeling model that combines internal and external labels. The model requires that all leaders are parallel to a given orientation θ∈[0,2π), whose value influences the geometric properties and hence the running times of our algorithms.

AB - Point feature map labeling is a geometric problem, in which a set of input points must be labeled with a set of disjoint rectangles (the bounding boxes of the label texts). Typically, labeling models either use internal labels, which must touch their feature point, or external (boundary) labels, which are placed on one of the four sides of the input points’ bounding box and which are connected to their feature points by crossing-free leader lines. In this paper we study polynomial-time algorithms for maximizing the number of internal labels in a mixed labeling model that combines internal and external labels. The model requires that all leaders are parallel to a given orientation θ∈[0,2π), whose value influences the geometric properties and hence the running times of our algorithms.

KW - CG, GD, GIS

U2 - 10.1007/978-3-319-18173-8_25

DO - 10.1007/978-3-319-18173-8_25

M3 - Conference contribution

SN - 978-3-319-18172-1

T3 - Lecture Notes in Computer Science

SP - 339

EP - 351

BT - Algorithms and Complexity

A2 - Paschos, Vangelis Th.

A2 - Widmayer, Peter

PB - Springer

ER -

Mixed Map Labeling

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this