Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane

DOI10.1142/S0218195916600049zbMath1409.68312MaRDI QIDQ2988724

Haitao Wang, Jing-Ru Zhang

Publication date: 19 May 2017

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

facility location problem\(k\)-means\(k\)-center\(k\)-median

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Related Items

Rearranging a sequence of points onto a line ⋮ Improved separated red-blue center clustering ⋮ The Coverage Problem by Aligned Disks ⋮ The coverage problem by aligned disks ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ An O(n log n)-Time Algorithm for the k-Center Problem in Trees ⋮ An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees

Cites Work

• Efficient algorithms for the one-dimensional \(k\)-center problem
• Fitting a step function to a point set
• A local search approximation algorithm for \(k\)-means clustering
• Optimal slope selection via expanders
• A linear-time algorithm for concave one-dimensional dynamic programming
• Improved complexity bounds for location problems on the real line
• Finding a minimum-weight \(k\)-link path in graphs with the concave Monge property and applications
• Optimal slope selection via cuttings
• A note on searching line arrangements and applications
• THE ALIGNED K-CENTER PROBLEM
• Approximation schemes for clustering problems
• Computing a Minimum Weightk-Link Path in Graphs with the Concave Monge Property
• Least squares quantization in PCM
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item