Constrained Boundary Labeling
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916724082737152 |
|---|---|
| author | Depian, Thomas Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus |
| author_facet | Depian, Thomas Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus |
| contents | Boundary labeling is a technique in computational geometry used to label sets of features in an illustration. It involves placing labels along an axis-parallel bounding box and connecting each label with its corresponding feature using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: Grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Furthermore, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions. Finally, we experimentally confirm that our approach has also practical relevance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_12245 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Constrained Boundary Labeling Depian, Thomas Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Computational Geometry Computational Complexity Boundary labeling is a technique in computational geometry used to label sets of features in an illustration. It involves placing labels along an axis-parallel bounding box and connecting each label with its corresponding feature using non-crossing leader lines. Although boundary labeling is well-studied, semantic constraints on the labels have not been investigated thoroughly. In this paper, we introduce grouping and ordering constraints in boundary labeling: Grouping constraints enforce that all labels in a group are placed consecutively on the boundary, and ordering constraints enforce a partial order over the labels. We show that it is NP-hard to find a labeling for arbitrarily sized labels with unrestricted positions along one side of the boundary. However, we obtain polynomial-time algorithms if we restrict this problem either to uniform-height labels or to a finite set of candidate positions. Furthermore, we show that finding a labeling on two opposite sides of the boundary is NP-complete, even for uniform-height labels and finite label positions. Finally, we experimentally confirm that our approach has also practical relevance. |
| title | Constrained Boundary Labeling |
| topic | Computational Geometry Computational Complexity |
| url | https://arxiv.org/abs/2402.12245 |