2026-07-23T19:18:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22153 2024-12-04T06:53:44Z ddc:004 open_access

Constrained Boundary Labeling Depian, Thomas Nöllenburg, Martin Terziadis, Soeren Wallinger, Markus Boundary labeling Grouping constraints Ordering constraints Boundary labeling is a technique in computational geometry used to label dense sets of feature points in an illustration. It involves placing labels along an axis-aligned bounding box and connecting each label with its corresponding feature point 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. Finally, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Depian and Martin Nöllenburg and Soeren Terziadis and Markus Wallinger 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.26 urn:nbn:de:0030-drops-221539 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.26 eng https://creativecommons.org/licenses/by/4.0/legalcode