Loading...
Please wait, while we are loading the content...
Similar Documents
Intersecting straight line segments with disks: complexity and approximation
| Content Provider | Semantic Scholar |
|---|---|
| Author | Kobylkin, K. S. Kobylkinks |
| Copyright Year | 2017 |
| Abstract | Computational complexity and approximability are studied for a problem of intersecting a set of straight line segments with the smallest cardinality set of disks of fixed radii r > 0 where the set of segments forms a straight line drawing G = (V,E) of a planar graph without edge crossings. Similar problems arise e.g. in network security applications (Agarwal et al., 2013). We claim strong NP-hardness of the problem within classes of (edge sets of) Delaunay triangulations, Gabriel graphs and other subgraphs (which are often used in network design) for r ∈ [dmin, ηdmax] and some constant η where dmax and dmin are Euclidean lengths of the longest and shortest graph edges respectively. Fast O(|E| log |E|)-time O(1)-approximation algorithm is proposed within the class of straight line drawings of planar graphs for which the inequality r ≥ ηdmax holds uniformly for some constant η > 0. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://ceur-ws.org/Vol-1894/mpr2.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
