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

DOI10.1145/2831230zbMATH Open1426.68273arXiv1409.7425OpenAlexW2235179049MaRDI QIDQ3177751FDOQ3177751

Authors: Benjamin Raichel, Sariel Har-Peled 

Publication date: 2 August 2018

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

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.

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

Recommendations

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

zbMATH Keywords

optimizationnetsclusteringlinear time

Mathematics Subject Classification ID

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

Cited In (10)

• High-dimensional approximate \(r\)-nets
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• A branch-and-bound method for the minimum \(k\)-enclosing ball problem
• Clustering with faulty centers
• A cubic-time algorithm for computing the trinet distance between level-1 networks
• Improved PTAS for the constrained \(k\)-means problem
• Light Euclidean Spanners with Steiner Points
• Data-driven invariant set for nonlinear systems with application to command governors
• Title not available (Why is that?)
• An ETH-Tight Exact Algorithm for Euclidean TSP

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)