Planar Support for Non-piercing Regions and Applications

DOI10.4230/LIPIcs.ESA.2018.69OpenAlexW2886902455MaRDI QIDQ5009639

Saurabh Ray, Rajiv Raman

Publication date: 4 August 2021

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2018/9532/

zbMATH Keywords

geometric optimizationpacking and coveringnon-piercing regions

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (7)

Existence of planar support for geometric hypergraphs using elementary techniques ⋮ Geometric stabbing via threshold rounding and factor revealing LPs ⋮ Conflict-free coloring of intersection graphs of geometric objects ⋮ Constructing planar support for non-piercing regions ⋮ Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. ⋮ Approximability of covering cells with line segments ⋮ A tight analysis of geometric local search

Cites Work

• Improved results on geometric hitting set problems
• Weighted geometric set cover via quasi-uniform sampling
• Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
• New existence proofs ε-nets

This page was built for publication: Planar Support for Non-piercing Regions and Applications