Efficiently approximating color-spanning balls

DOI10.1016/J.TCS.2016.04.022zbMATH Open1339.68272OpenAlexW2361557697MaRDI QIDQ284593FDOQ284593

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

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

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)

Cites Work

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

Cited In (5)

• Color-spanning localized query
• 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
• Approximation algorithms for color spanning diameter

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)