THE ALIGNED K-CENTER PROBLEM

DOI10.1142/S0218195911003597zbMath1216.65022OpenAlexW2158196818MaRDI QIDQ2999091

Antoine Vigneron, Hyeon-Suk Na, Chan-Su Shin, Christian Knauer, Peter Brass

Publication date: 11 May 2011

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

Full work available at URL: https://doi.org/10.1142/s0218195911003597

zbMATH Keywords

randomized algorithmapproximate algorithm\(k\)-center problem

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (10)

Computing the Rectilinear Center of Uncertain Points in the Plane ⋮ Improved separated red-blue center clustering ⋮ The Coverage Problem by Aligned Disks ⋮ The coverage problem by aligned disks ⋮ Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane ⋮ Efficient algorithms for the one-dimensional \(k\)-center problem ⋮ Computing the center of uncertain points on tree networks ⋮ Computing the Line-Constrained k-center in the Plane for Small k ⋮ 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

• Base station placement on boundary of a convex polygon
• Constrained minimum enclosing circle with center on a query line segment
• Fast computation of smallest enclosing circle with center on a query line segment
• Optimal packing and covering in the plane are NP-complete
• Randomized optimal algorithm for slope selection
• The slab dividing approach to solve the Euclidean \(P\)-center problem
• Maintenance of a piercing set for intervals with applications
• Exact and approximation algorithms for clustering
• Geometric applications of a randomized optimization technique
• A data structure for dynamic trees
• Clustering motion
• On the complexity of some geometric problems in unbounded dimension
• On the Complexity of Some Common Geometric Location Problems
• Generalized Selection and Ranking: Sorted Matrices
• VARIATIONS OF BASE-STATION PLACEMENT PROBLEM ON THE BOUNDARY OF A CONVEX REGION
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• An Optimal-Time Algorithm for Slope Selection
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS

This page was built for publication: THE ALIGNED K-CENTER PROBLEM