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.
back to list