Algorithm Design and Analysis for Simultaneous Boundary Labeling

In boundary labeling, each feature point is connected to a label placed on the boundary of a rectangular image by a leader, which may be a rectilinear or a straight line segment. Currently, all the research about boundary labeling focuses on how to generate label placements for one image with high readability. However, there may be a series of related images, which share all, or parts of the same feature and label set, need to be labeled. If we calculate label placements for each image separately, it is hard to keep track of the relationship between images. To overcome the above difficulty, in this thesis we propose a new problem called simultaneous boundary labeling. We keep the relationship between images by limiting common features and labels of a series of images in the same place, and find a common label placement for all images with minimal leader crossing number and minimal total leader length to increase the readability. We design some heuristic algorithms when there are two related images need to be labeled and show the problem to be NP-complete when there are more than four images in the series. The leader length minimization problem can be solved by a weighted bipartite matching algorithm.