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).
