Shooting Bricks with Orthogonal Laser Beams: A First Step towards Internal External Map Labeling

We are given a set A of points and a set B of axis-aligned equal size rectangles in a larger rectangle R in the plane. We call the points in A aliens and the rectangles in B bricks, and assume that each alien can shoot an orthogonal laser beam with one bend that first travels vertically and then horizontally. Any bricks hit by a laser beam are destroyed. In order to escape from their prison, each alien has to shoot one laser beam that leaves R on the right side and their joint goal is to destroy as few bricks as possible to conserve their limited power supply. We study several variants by restricting the possible layouts of lasers and bricks, and provide both algorithms and hardness results. Our results are a first step towards solving an open map labeling problem, where labels can be placed either internally in the map or externally on the right side of the boundary of the map by using orthogonal leaders connecting points and labels.