A simple linear algorithm for computing rectilinear 3-centers

DOI10.1016/J.COMGEO.2004.12.002MaRDI QIDQ2486079zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• A linear-time algorithm for the geodesic center of a simple polygon
• scientific article; zbMATH DE number 6789192
• Approximation algorithms for orthogonal line centers
• Approximation algorithms for orthogonal line centers
• Computing a centerpoint of a finite planar set of points in linear time
• A near-linear algorithm for the planar segment-center problem
• scientific article; zbMATH DE number 1003238
• An optimal algorithm for the rectilinear link center of a rectilinear polygon
• scientific article; zbMATH DE number 177553
• A near-linear algorithm for the planar 2-center problem

Cites work

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

Cited in

(10)

• New algorithms for \(k\)-center and extensions
• New Algorithms for k-Center and Extensions
• Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares
• An optimal approximation algorithm for the rectilinear m-center problem
• 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
• Rectilinear covering for imprecise input points (extended abstract)
• scientific article; zbMATH DE number 1728311 (Why is no real title available?)
• Computing the line-constrained \(k\)-center in the plane for small \(k\)
• The \(p\)-center problem under locational uncertainty of demand points

Describes a project that uses

Uses Software

• CGAL

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

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