Approximation algorithms for a k-line center

DOI10.1007/S00453-005-1166-XMaRDI QIDQ818652zbMATH OpenOpenAlexFDO

Authors Pankaj K. Agarwal, Cecilia M. Procopiuc, Kasturi Varadarajan

Publication date 21 March 2006

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-005-1166-x

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• scientific article; zbMATH DE number 1947381
• Approximation algorithms for orthogonal line centers
• Approximation algorithms for orthogonal line centers
• An approximation algorithm for \(k\)-center problem on a convex polygon
• Efficient algorithms for the weighted \(k\)-center problem on a real line
• An optimal approximation algorithm for the rectilinear m-center problem
• scientific article; zbMATH DE number 1003238
• A near-linear algorithm for the planar segment-center problem
• A (\(1+{\varepsilon}\))-approximation algorithm for 2-line-center
• scientific article; zbMATH DE number 2089224

Cited in

(16)

• Practical methods for shape fitting and kinetic data structures using coresets
• New algorithms for \(k\)-center and extensions
• A technique for obtaining true approximations for \(k\)-center with covering constraints
• Efficient approximation algorithms for clustering point-sets
• THE ALIGNED K-CENTER PROBLEM
• A near-linear algorithm for the planar 2-center problem
• Clustering geometrically-modeled points in the aggregated uncertainty model
• A linear time deterministic algorithm to find a small subset that approximates the centroid
• scientific article; zbMATH DE number 1947381 (Why is no real title available?)
• Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane
• A linear time approximation scheme for computing geometric maximum \(k\)-star
• scientific article; zbMATH DE number 2089224 (Why is no real title available?)
• scientific article; zbMATH DE number 1445346 (Why is no real title available?)
• Approximation algorithms for orthogonal line centers
• Minimum-width double-slabs and widest empty slabs in high dimensions
• Approximation algorithms for orthogonal line centers

This page was built for publication: Approximation algorithms for a \(k\)-line center

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