DSpace Repository

Algorithms for Boundary Labeling of Horizontal Line Segments

Show simple item record

dc.contributor.author Kurmi, Abhilash
dc.date.accessioned 2021-08-02T06:03:56Z
dc.date.available 2021-08-02T06:03:56Z
dc.date.issued 2019-06
dc.identifier.citation 46p. en_US
dc.identifier.uri http://hdl.handle.net/10263/7172
dc.description Dissertation under the supervision of Dr. Sasanka Roy, Associate Professor, ACMU en_US
dc.description.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). en_US
dc.language.iso en en_US
dc.publisher Indian Statistical Institute, Kolkata en_US
dc.relation.ispartofseries Dissertation;;2020-18
dc.subject Multi-Sided Boundary Labeling problem en_US
dc.subject Time and Space Complexity en_US
dc.title Algorithms for Boundary Labeling of Horizontal Line Segments en_US
dc.type Other en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Advanced Search

Browse

My Account