On the approximability of covering points by lines and related problems
From MaRDI portal
Publication:904111
DOI10.1016/j.comgeo.2015.06.006zbMath1335.65029arXiv1312.2549OpenAlexW1582081577MaRDI QIDQ904111
Adrian Dumitrescu, Ming-Hui Jiang
Publication date: 15 January 2016
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.2549
computational complexitygreedy algorithmNP-hardnessAPX-hardnessgeometric set covermaximum coveragecovering points by linescovering tour problemgeometric toursHamiltonian tour problem
Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)
Related Items
Novel geometric approach for virtual coiling, How to Block Blood Flow by Using Elastic Coil, Geometric hitting set for segments of few orientations, Rainbow polygons for colored point sets in the plane
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- A parameterized algorithm for the hyperplane-cover problem
- Approximation algorithms for a geometric set cover problem
- Improved results on geometric hitting set problems
- A non-linear lower bound for planar epsilon-nets
- Improved approximation algorithms for geometric set cover
- Minimum-link watchman tours
- Hitting sets when the VC-dimension is small
- \(\epsilon\)-nets and simplex range queries
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- On the complexity of locating linear facilities in the plane
- Shortest paths of bounded curvature in the plane
- Almost optimal set covers in finite VC-dimension
- Angle-restricted tours in the plane.
- Covering things with things
- Algorithmic construction of sets for k -restrictions
- A threshold of ln n for approximating set cover
- A Greedy Heuristic for the Set-Covering Problem
- On the hardness of approximating minimization problems
- A Tight Analysis of the Greedy Algorithm for Set Cover
- Tight lower bounds for the size of epsilon-nets
- Point Line Cover: The Easy Kernel is Essentially Tight
- Optimal Covering Tours with Turn Costs
- On Covering Points with Minimum Turns
- Traversing a set of points with a minimum number of turns
