Applications of incidence bounds in point covering problems

DOI10.4230/LIPICS.SOCG.2016.60MaRDI QIDQ3132896zbMATH OpenFDO

Authors Peyman Afshani, Edvin Berglin, Ingo van Duijn, Jesper Sindahl Nielsen

Publication date 30 January 2018

Full work available at URL https://arxiv.org/abs/1603.07282

zbMATH Keywords

exponential algorithmincidence boundsinclusion exclusionpoint cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A parameterized algorithm for the hyperplane-cover problem
• Tight kernels for covering and hitting: point hyperplane cover and polynomial point hitting set
• Covering a Set of Points with a Minimum Number of Lines
• Reduction rules deliver efficient FPT-algorithms for covering points with lines
• Covering lattice points by subspaces and counting point-hyperplane incidences

Cited in

(12)

• Nondegenerate spheres in four dimensions
• Modelling of ``green investments risks
• Two theorems on point-flat incidences
• Kernelization of the subset general position problem in geometry
• Geometric covering number: covering points with curves
• Extending Erdős-Beck's theorem to higher dimensions
• A parameterized algorithm for the hyperplane-cover problem
• Point line cover: the easy kernel is essentially tight
• Reduction rules deliver efficient FPT-algorithms for covering points with lines
• Tight kernels for covering and hitting: point hyperplane cover and polynomial point hitting set
• On the approximability of covering points by lines and related problems
• Nearly time-optimal kernelization algorithms for the line-cover problem with big data

This page was built for publication: Applications of incidence bounds in point covering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132896)