Net and prune: a linear time algorithm for Euclidean distance problems

DOI10.1145/2831230MaRDI QIDQ3177751zbMATH OpenOpenAlexFDO

Authors Benjamin Raichel, Sariel Har-Peled

Publication date 2 August 2018

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.7425

zbMATH Keywords

clusteringlinear timenetsoptimization

Mathematics Subject Classification ID

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

Abstract: We provide a general framework for getting expected linear time constant factor approximations (and in many cases FPTAS's) to several well known problems in Computational Geometry, such as $k$-center clustering and farthest nearest neighbor. The new approach is robust to variations in the input problem, and yet it is simple, elegant and practical. In particular, many of these well studied problems which fit easily into our framework, either previously had no linear time approximation algorithm, or required rather involved algorithms and analysis. A short list of the problems we consider include farthest nearest neighbor, $k$-center clustering, smallest disk enclosing $k$ points, $k$th largest distance, $k$th smallest $m$-nearest neighbor distance, $k$th heaviest edge in the MST and other spanning forest type problems, problems involving upward closed set systems, and more. Finally, we show how to extend our framework such that the linear running time bound holds with high probability.

Recommendations

• Net and prune: a linear time algorithm for Euclidean distance problems
• Linear-time approximation schemes for clustering problems in any dimensions
• scientific article; zbMATH DE number 177542
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions

Cited in

(15)

• High-dimensional approximate \(r\)-nets
• A branch-and-bound method for the minimum \(k\)-enclosing ball problem
• Improved PTAS for the constrained \(k\)-means problem
• Approximation algorithms for polynomial-expansion and low-density graphs
• A cubic-time algorithm for computing the trinet distance between level-1 networks
• Net and prune: a linear time algorithm for Euclidean distance problems
• Light Euclidean Spanners with Steiner Points
• Clustering with faulty centers
• An ETH-Tight Exact Algorithm for Euclidean TSP
• A note on reachability and distance oracles for transmission graphs
• Data-driven invariant set for nonlinear systems with application to command governors
• Data-driven high-order control barrier functions via optimization-based approaches
• Data-driven certified control barrier functions
• Faster approximation scheme for Euclidean k-TSP
• Near optimal locality sensitive orderings in Euclidean space

This page was built for publication: Net and prune: a linear time algorithm for Euclidean distance problems

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