Name
Abstract | ||
|---|---|---|
Korman et al. [18] studied the following geometric covering problem: given a set S of n line segments in the plane, find a minimum number of line segments such that every cell in the arrangement of the line segments is covered. Here, a line segment s covers a cell f if s is incident to f. The problem was shown to be NP-hard, even if the line segments in S are axis-parallel, and it remains NP-hard when the goal is to cover the “rectangular” cells (i.e., cells that are defined by exactly four axis-parallel line segments). |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1016/j.tcs.2019.05.004 | Theoretical Computer Science |
Keywords | DocType | Volume |
Geometric covering,Line segment covering,Approximation algorithms,APX-hardness,PTAS,Fixed-parameter tractability | Conference | 784 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
5 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paz Carmi | 1 | 321 | 43.14 |
| Anil Maheshwari | 2 | 869 | 104.47 |
| Saeed Mehrabi 0001 | 3 | 28 | 7.00 |
| Luís Fernando Schultz Xavier da Silveira | 4 | 0 | 0.34 |
| Xavier Da Silveira | 5 | 0 | 0.34 |