On the approximability of covering points by lines and related problems

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

zbMATH Keywords

computational complexitygreedy algorithmNP-hardnessAPX-hardnessgeometric set covermaximum coveragecovering points by linescovering tour problemgeometric toursHamiltonian tour problem

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Complexity and performance of numerical algorithms (65Y20)

Related Items (4)

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

This page was built for publication: On the approximability of covering points by lines and related problems