Shooting Bricks with Orthogonal Laser Beams: A First Step towards Internal/External Map Labeling
Maarten Loer, Martin Nöllenburg · Canadian Conference on Computational Geometry · 2010
We study several variants of a hybrid map labeling problem that combines the following two tasks: (i) a set A of points in a rectangle R needs to be labeled with rectangular labels on the right boundary of R using (axisaligned) orthogonal one-bend polylines called leaders to connect points and labels; (ii) a maximum subset B 0 of a set B of xed internal congruent rectangular labels in R needs to be selected such that B 0 is an independent set of labels and no leader intersects any label in B 0 . We also call the points in A aliens, the labels of B bricks, and the leaders laser beams. Then the problem translates into every alien shooting a laser beam so that in total as few bricks as possible are destroyed. We provide algorithms and NP-hardness results for dierent variants of the problem.