Please use this identifier to cite or link to this item: http://hdl.handle.net/10263/7172
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKurmi, Abhilash-
dc.date.accessioned2021-08-02T06:03:56Z-
dc.date.available2021-08-02T06:03:56Z-
dc.date.issued2019-06-
dc.identifier.citation46p.en_US
dc.identifier.urihttp://hdl.handle.net/10263/7172-
dc.descriptionDissertation under the supervision of Dr. Sasanka Roy, Associate Professor, ACMUen_US
dc.description.abstractIn 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.isoenen_US
dc.publisherIndian Statistical Institute, Kolkataen_US
dc.relation.ispartofseriesDissertation;;2020-18-
dc.subjectMulti-Sided Boundary Labeling problemen_US
dc.subjectTime and Space Complexityen_US
dc.titleAlgorithms for Boundary Labeling of Horizontal Line Segmentsen_US
dc.typeOtheren_US
Appears in Collections:Dissertations - M Tech (CS)

Files in This Item:
File Description SizeFormat 
MTech_CS1621-Thesis-Abhilash Kurmi.pdf679.05 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.