A faster algorithm for the two-center decision problem

DOI10.1016/0020-0190(93)90153-ZMaRDI QIDQ685492zbMATH OpenOpenAlexFDO

Authors John Hershberger

Publication date 17 October 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90153-z

zbMATH Keywords

clustering\(k\)-center problem

Mathematics Subject Classification ID

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

Recommendations

• A fast algorithm for the alpha-connected two-center decision problem
• More planar two-center algorithms
• Efficient planar two-center algorithms
• Simple \(O(n \log^{2} n)\) algorithms for the planar 2-center problem
• The discrete 2-center problem

Cites work

• scientific article; zbMATH DE number 432848 (Why is no real title available?)
• A linear-time algorithm for a special case of disjoint set union
• Finding tailored partitions
• Geometric clusterings
• On a circle placement problem
• On the Complexity of Some Common Geometric Location Problems
• On the shape of a set of points in the plane

Cited in

(16)

• Improved algorithms for the bichromatic two-center problem for pairs of points
• Efficient planar two-center algorithms
• 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
• The mixed center location problem
• The 2-mixed-center color spanning problem
• Efficient \(k\)-center algorithms for planar points in convex position
• A sweepline algorithm to solve the two-center problem
• The Mixed Center Location Problem
• An efficient algorithm for the proximity connected two center problem
• The 2-center problem in three dimensions
• BOUNDED-VELOCITY APPROXIMATION OF MOBILE EUCLIDEAN 2-CENTRES
• On the planar two-center problem and circular hulls
• Discrete and mixed two-center problems for line segments
• A fast algorithm for the alpha-connected two-center decision problem

This page was built for publication: A faster algorithm for the two-center decision problem

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