Efficiently approximating color-spanning balls

DOI10.1016/J.TCS.2016.04.022MaRDI QIDQ284593zbMATHOpenAlexFDO

Authors Payam Khanteimouri, Ali Mohades, Mohammad A. Abam, M. R. Kazemi

Publication date 18 May 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2016.04.022

zbMATH Keywords

complexityapproximation algorithmscolor-spanning objects

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• An Approximation Algorithm for the Smallest Color-Spanning Circle Problem
• On approximability of minimum color-spanning ball in high dimensions
• The approximation algorithms for a class of multiple-choice problem
• Color-spanning localized query
• Computing minimum diameter color-spanning sets

Cites work

• scientific article; zbMATH DE number 1875422 (Why is no real title available?)
• scientific article; zbMATH DE number 6472586 (Why is no real title available?)
• A near-linear algorithm for the planar 2-center problem
• A simple randomized sieve algorithm for the closest-pair problem
• An optimal algorithm for approximate nearest neighbor searching fixed dimensions
• Computing the smallest color-spanning axis-parallel square
• Faster core-set constructions and data stream algorithms in fixed dimensions
• Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization
• Generalized Selection and Ranking: Sorted Matrices
• Lower bounds based on the exponential time hypothesis
• On enclosing k points by a circle
• On the complexity of \(k\)-SAT
• On the possibility of faster \textsc{SAT} algorithms
• On the rectangularp-center problem
• Shortest color-spanning intervals
• The upper envelope of Voronoi surfaces and its applications
• Which problems have strongly exponential complexity?

Cited in

(5)

• The approximation algorithms for a class of multiple-choice problem
• An Approximation Algorithm for the Smallest Color-Spanning Circle Problem
• On approximability of minimum color-spanning ball in high dimensions
• Approximation algorithms for color spanning diameter
• Color-spanning localized query

This page was built for publication: Efficiently approximating color-spanning balls

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