Faster algorithms for some optimization problems on collinear points

DOI10.4230/LIPICS.SOCG.2018.8zbMATH Open1489.68339MaRDI QIDQ5115775FDOQ5115775

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

Publication date: 18 August 2020

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

zbMATH Keywords

range assignmentcollinear points

Mathematics Subject Classification ID

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

Cites Work

• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Polynomial time approximation schemes for base station coverage with minimum total radii
• Algorithms – ESA 2005
• Minimum-cost coverage of point sets by disks
• Connecting a set of circles with minimum sum of radii
• The minimum-area spanning tree problem
• Range assignment of base-stations maximizing coverage area without interference
• Title not available (Why is that?)

Cited In (5)

• Algorithms for the line-constrained disk coverage and related problems
• Algorithms for the line-constrained disk coverage and related problems
• Title not available (Why is that?)
• On the line-separable unit-disk coverage and related problems
• Range assignment of base-stations maximizing coverage area without interference

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)