Algorithms for Boundary Labeling of Horizontal Line Segments

Abstract

In boundary labelling problem the target is to labeling a set P of n points in the plane with labels that are aligned to side of the bounding box of P . In this work, we investigate a variant of this problem. In our problem, we consider a set of sites inside a rectangle R and label are placed in the compliment of R and touches the left boundary of it. Labels are axis- parallel rectangles of same size and no two labels overlaps. We introduce a set V , called visibility , which is a set of subsets of labels correspond to points of sites. Before connecting site (say p) at point (say p1 2 p) with some label (say l), first we need to check weather subset of label correspond to p1 is in set V or not. If it is then we check the label l belongs to that subset of label or not. If it contains that label then we can join site to the label, otherwise not. In our problem we used po-leaders, that is starting from site it is parallel to the side of R where its label resides and then orthogonal to that side of R. We considered various geometric objects as sites, such as point, same length horizontal segment, different length horizontal segments. As a solution, we derive a dynamic algorithm that minimizes the arbitrary cost function and give us planar solution where sites connects to labels by po- leaders and induces a matching such that no two po-leader intersects, also no two leaders shares common site (or label) and every leader satisfies visibility V . For points as sites, our dynamic algorithm runs in O(n3) time and optimizes the cost function. This running time also same for the case of unit length horizontal line segments as sites. Then we taken arbitrary length horizontal segment, algorithms runs in O(n4) time. We assumed that only one end point of any horizontal line segment can be used to connect label (by po-leader).