Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set

DOI10.1145/2261250.2261293zbMath1293.05101OpenAlexW1994213977MaRDI QIDQ2874591

Timothy M. Chan

Publication date: 7 August 2014

Published in: Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2261250.2261293

zbMATH Keywords

independent setcombinatorial geometryapproximation algorithmsconflict-free coloringrange spaces

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (6)

Coloring points with respect to squares ⋮ Geometric Packing under Nonuniform Constraints ⋮ Geometric stabbing via threshold rounding and factor revealing LPs ⋮ Coloring Delaunay-edges and their generalizations ⋮ Hitting and Piercing Rectangles Induced by a Point Set ⋮ Conflict-free coloring of string graphs

This page was built for publication: Conflict-free coloring of points with respect to rectangles and approximation algorithms for discrete independent set