Haunert, Haverkort, Niedermann, Nocaj, Slingsby and Wood – LABELING CURVES WITH CURVED LABELS 2014

Description

The paper studies labeling point features along a single smooth, directed curve (e.g., a metro line) using curved labels—”fat” curves of fixed width and length that begin at stops and end at predefined ports on the region boundary. Curved labels improve readability, aesthetic consistency, and packing compared with straight labels. A valid labeling maps each stop injectively to a port such that labels do not intersect the central curve, the boundary, or each other. Labels are modeled as fixed shapes (e.g., cubic Bézier curves). The authors focus on minimizing switchovers—adjacent stops connected to ports on opposite sides of the curve. For the one-sided case (all ports on one border) they give a dynamic programming test for existence in O(n m^2) time and O(n+m) space. For the two-sided case they reduce to combinations of one-sided instances and obtain an optimal-labeling algorithm in O(n^2 m^4) time and O(n m^2) space. Future work includes experiments, port placement, tuning, and handling multiple lines (possible NP-hardness).