A simple linear algorithm for computing rectilinear 3-centers

DOI10.1016/j.comgeo.2004.12.002zbMath1115.68156OpenAlexW2087653366MaRDI QIDQ2486079

Yanyan Li

Publication date: 5 August 2005

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2004.12.002

zbMATH Keywords

Facility locationGeometric optimizationRectilinear center

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Related Items (7)

New algorithms for \(k\)-center and extensions ⋮ Computing the Rectilinear Center of Uncertain Points in the Plane ⋮ Efficient algorithms for computing one or two discrete centers hitting a set of line segments ⋮ The \(p\)-center problem under locational uncertainty of demand points ⋮ Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares ⋮ Computing the Line-Constrained k-center in the Plane for Small k ⋮ New Algorithms for k-Center and Extensions

Uses Software

• CGAL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On weighted rectilinear 2-center and 3-center problems
• On piercing sets of axis-parallel rectangles and rings
• An optimal approximation algorithm for the rectilinear m-center problem
• Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance
• The discrete 2-center problem
• A near-linear algorithm for the planar 2-center problem
• Time bounds for selection
• Exact and approximation algorithms for clustering
• A subexponential bound for linear programming
• More planar two-center algorithms
• Discrete rectilinear 2-center problems
• The 2-Center Problem with Obstacles
• The Weighted Euclidean 1-Center Problem
• On the Complexity of Some Common Geometric Location Problems
• Generalized Selection and Ranking: Sorted Matrices
• An O(nlogn) randomizing algorithm for the weighted euclidean 1-center problem
• Linear Programming in Linear Time When the Dimension Is Fixed
• The Capacitated K-Center Problem
• On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
• On the rectangularp-center problem
• Finding kth paths and p-centers by generating and searching good data structures
• 3-PIERCING OF d-DIMENSIONAL BOXES AND HOMOTHETIC TRIANGLES
• The computational geometry algorithms library CGAL

This page was built for publication: A simple linear algorithm for computing rectilinear 3-centers