Faster algorithms for some optimization problems on collinear points

DOI10.4230/LIPICS.SOCG.2018.8MaRDI QIDQ5115775zbMATH OpenFDO

Authors Ahmad Biniaz, Prosenjit Bose, Paz Carmi, Anil Maheshwari, J. Ian Munro, Michiel Smid

Publication date 18 August 2020

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2018.8

zbMATH Keywords

range assignmentcollinear points

Mathematics Subject Classification ID

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

Recommendations

• Faster algorithms for some optimization problems on collinear points
• Algorithms for the line-constrained disk coverage and related problems
• A note on minimum-sum coverage by aligned disks
• Covering moving points with anchored disks
• Covering many or few points with unit disks

Cites work

• Algorithms – ESA 2005
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Faster algorithms for some optimization problems on collinear points
• Minimum-cost coverage of point sets by disks
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Range assignment of base-stations maximizing coverage area without interference
• The minimum-area spanning tree problem

Cited in

(10)

• Algorithms for the line-constrained disk coverage and related problems
• Algorithms for the line-constrained disk coverage and related problems
• On line-separable weighted unit-disk coverage and related problems
• Faster algorithms for some optimization problems on collinear points
• Faster algorithms for some optimization problems on collinear points
• On the line-separable unit-disk coverage and related problems
• On line-separable weighted unit-disk coverage and related problems
• Range assignment of base-stations maximizing coverage area without interference
• On the line-separable unit-disk coverage and related problems
• Maximum centre-disjoint mergeable disks

This page was built for publication: Faster algorithms for some optimization problems on collinear points

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