Color Spanning Objects - Algorithms and Hardness Results

Show simple item record

dc.contributor.author Banerjee, Sandip
dc.contributor.author Misra, Neeldhara
dc.contributor.author Nandy, Subhas C.
dc.contributor.other International Conference on Algorithms and Discrete Applied Mathematics (CALDAM)
dc.coverage.spatial Kanpur, IN
dc.date.accessioned 2016-04-16T11:19:01Z
dc.date.available 2016-04-16T11:19:01Z
dc.date.issued 2016-02-08
dc.identifier.citation Banerjee, Sandip; Misra, Neeldhara and Nandy, Subhas C., “Color Spanning Objects - Algorithms and Hardness Results”, in the International Conference on Algorithms and Discrete Applied Mathematics (CALDAM), Indian Institute of Technology Kanpur, IN, Feb. 8-10, 2016. en_US
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/2180
dc.identifier.uri http://dx.doi.org/10.1007/978-3-319-29221-2_4
dc.description.abstract In this paper, we study the Shortest Color Spanning Intervals problem, and related generalizations, namely Smallest Color Spanning t Squares and Smallest Color Spanning t Circles. The generic setting is the following: we are given n points in the plane (or on the line), each colored with one of k colors, and for each color i we also have a demand si. Given a budget t, we are required to find at most t objects (for example, intervals, squares, circles, etc.) that cover at least si points of color i. Typically, the goal is to minimize the maximum perimeter or area. We provide exact algorithms for these problems for the cases of intervals, circles and squares, generalizing several known results. In the case of intervals, we provide a comprehensive understanding of the complexity landscape of the problem after taking several natural parameters into account. Given that the problem turns out to be W[1]-hard parameterized by the standard parameters, we introduce a new parameter, namely sparsity, and prove new hardness and tractability results in this context. For squares and circles, we use existing algorithms of one smallest color spanning object in order to design algorithms for getting t identical objects of minimum size whose union spans all the colors. en_US
dc.description.statementofresponsibility by Sandip Banerjee, Neeldhara Misra and Subhas C. Nandy
dc.language.iso en_US en_US
dc.publisher Springer en_US
dc.subject Color spanning sets en_US
dc.subject Computational geometry en_US
dc.subject Parameterized complexity en_US
dc.subject Exact algorithms en_US
dc.title Color Spanning Objects - Algorithms and Hardness Results en_US
dc.type Article en_US


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account