An Approximation Algorithm for the Smallest Color-Spanning Circle Problem

DOI10.1007/978-3-319-21398-9_14MaRDI QIDQ3196382zbMATH OpenOpenAlexFDO

Authors Yin Wang, Yinfeng Xu

Publication date 29 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-21398-9_14

zbMATH Keywords

approximation algorithmcomputational geometrycolored setminimum diameter color-spanning set problem

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Recommendations

• Approximation algorithms for color spanning diameter
• An approximation algorithm for circular arc colouring
• Computing minimum diameter color-spanning sets
• An approximate algorithm for the \( (k,d)\)-coloring problem
• scientific article; zbMATH DE number 3889546
• Approximation algorithms for the interval constrained coloring problem
• Efficiently approximating color-spanning balls
• scientific article; zbMATH DE number 2085002
• On approximability of minimum color-spanning ball in high dimensions
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 1875422 (Why is no real title available?)
• Computing minimum diameter color-spanning sets
• Euclidean minimum spanning trees and bichromatic closest pairs
• Fast computation of smallest enclosing circle with center on a query line segment
• Finding minimum area \(k\)-gons
• Iterated nearest neighbors and finding minimal polytopes
• On some geometric problems of color-spanning sets
• Sets with No Empty Convex 7-Gons

Cited in

(6)

• Efficiently approximating color-spanning balls
• Minimum width color spanning annulus
• Minimum width color spanning annulus
• A better heuristic algorithm for finding the closest trio of 3-colored points from a given set of 3-colored points on a plane
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• The approximation algorithms for a class of multiple-choice problem

This page was built for publication: An Approximation Algorithm for the Smallest Color-Spanning Circle Problem

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