A linear time deterministic algorithm to find a small subset that approximates the centroid

DOI10.1016/J.IPL.2007.07.008MaRDI QIDQ2380033zbMATH OpenOpenAlexFDO

Authors Pratik Worah, Sandeep Sen

Publication date 24 March 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2007.07.008

zbMATH Keywords

clusteringcomputational geometryderandomization

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Approximation algorithms for a \(k\)-line center
• scientific article; zbMATH DE number 1947381
• Computing a centerpoint of a finite planar set of points in linear time
• A simple linear-time algorithm for computing the center of an interval graph
• Linear time algorithm for 1-center in \(\mathfrak {R}^d\) under convex polyhedral distance function
• Efficient algorithms for computing one or two discrete centers hitting a set of line segments
• scientific article; zbMATH DE number 1003238
• An optimal approximation algorithm for the rectilinear m-center problem
• A near-linear algorithm for the planar segment-center problem
• Approximate center points in dense point sets

Cites work

• On graph problems in a semi-streaming model

This page was built for publication: A linear time deterministic algorithm to find a small subset that approximates the centroid

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