On approximability of minimum color-spanning ball in high dimensions

DOI10.1016/j.dam.2019.10.016zbMath1473.68202OpenAlexW2990455488MaRDI QIDQ2181229

Payam Khanteimouri, Ali Mohades, Mohammad Reza Kazemi

Publication date: 18 May 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.10.016

zbMATH Keywords

approximation algorithmapproximabilityexponential time hypothesis (ETH)color-spanning sethigh-dimensional spaces

Mathematics Subject Classification ID

Database theory (68P15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (2)

On the \(k\)-colored rainbow sets in fixed dimensions ⋮ Clustering Geometrically-Modeled Points in the Aggregated Uncertainty Model

Cites Work

• Efficiently approximating color-spanning balls
• Approximation algorithms for color spanning diameter
• Computing minimum diameter color-spanning sets is hard
• Approximate minimum diameter
• Optimal core-sets for balls

This page was built for publication: On approximability of minimum color-spanning ball in high dimensions