Simple O(n ^2 n) algorithms for the planar 2-center problem

DOI10.1007/978-3-319-62389-4_40MaRDI QIDQ2412430zbMATH OpenOpenAlexFDO

Authors Xuehou Tan, Bo Jiang

Publication date 23 October 2017

Full work available at URL https://doi.org/10.1007/978-3-319-62389-4_40

zbMATH Keywords

computational geometryconvex polygonsplanar 2-center problemsmallest enclosing circle problem

Mathematics Subject Classification ID

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

Recommendations

• A near-linear algorithm for the planar 2-center problem
• Efficient planar two-center algorithms
• More planar two-center algorithms
• An Algorithm for the p-Center Problem in the Plane
• A near-linear algorithm for the planar segment-center problem
• scientific article; zbMATH DE number 1003238
• scientific article; zbMATH DE number 1696646
• Approximating k-center in planar graphs
• An O(n n) algorithm for computing a link center in a simple polygon

Cited in

(12)

• A near-linear algorithm for the planar 2-center problem
• Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares
• More planar two-center algorithms
• A geometric proof of the combinatorial bounds for the number of optimal solutions for the Euclidean 2-center problem
• On the planar two-center problem and circular hulls
• Efficient planar two-center algorithms
• On the planar two-center problem and circular hulls
• Discrete and mixed two-center problems for line segments
• A faster algorithm for the two-center decision problem
• Optimal algorithm for the planar two-center problem
• An optimal and practical algorithm for the planar 2-center problem
• Optimal algorithm for the planar two-center problem

This page was built for publication: Simple \(O(n \log^{2} n)\) algorithms for the planar 2-center problem

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