Paper Info
Title
Color Spanning Objects: Algorithms and Hardness Results.
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 $$s_i$$. Given a budget t, we are required to find at most t objects for example, intervals, squares, circles, etc. that cover at least $$s_i$$ 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.
Year
DOI
Venue
2016
10.1007/978-3-319-29221-2_4
CALDAM
Keywords
Field
DocType
Color spanning sets,Computational geometry,Parameterized complexity,Exact algorithms
Discrete mathematics,Parameterized complexity,Colored,Combinatorics,Generalization,Algorithm,Perimeter,Mathematics
Conference
Volume
ISSN
Citations 
9602
0302-9743
0
PageRank 
References 
Authors
0.34
7
3
Name
Order
Citations
PageRank
Sandip Banerjee100.68
Neeldhara Misra234131.42
Subhas C. Nandy328549.55