The discrete 2-center problem

DOI10.1007/PL00009387MaRDI QIDQ1272957zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Emo Welzl, Pankaj K. Agarwal, Micha Sharir

Publication date 19 April 1999

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00009387

zbMATH Keywords

discrete 2-center

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• A near-linear algorithm for the planar 2-center problem
• More planar two-center algorithms
• Efficient planar two-center algorithms
• A faster algorithm for the two-center decision problem

Cited in

(43)

• A fast algorithm for the alpha-connected two-center decision problem
• A sweepline algorithm to solve the two-center problem
• A (\(1+{\varepsilon}\))-approximation algorithm for 2-line-center
• Facility location and the geometric minimum-diameter spanning tree.
• The mixed center location problem
• Time-dependent green Weber problem
• A polynomial-time optimization algorithm for a rectilinear partitioning problem with applications in VLSI design automation.
• The 2-center problem in three dimensions
• A geometric proof of the combinatorial bounds for the number of optimal solutions for the Euclidean 2-center problem
• Discrete rectilinear 2-center problems
• On the planar two-center problem and circular hulls
• Efficient planar two-center algorithms
• Parametric search: three new applications
• The most points connected-covering problem with two disks
• Efficient algorithms for computing one or two discrete centers hitting a set of line segments
• The discrete and mixed minimax 2-center problems
• A simple linear algorithm for computing rectilinear 3-centers
• scientific article; zbMATH DE number 1588326 (Why is no real title available?)
• scientific article; zbMATH DE number 1696646 (Why is no real title available?)
• The 2-center problem with obstacles
• Syzygies in the two center problem
• Computing the line-constrained k-center in the plane for small k
• On clustering to minimize the sum of radii
• The Mixed Center Location Problem
• Covering and piercing disks with two centers
• Computing a Segment Center for a Planar Point Set
• A FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM
• The discrete and mixed minimax 2-center problem
• An Efficient Algorithm for 2D Euclidean 2-Center with Outliers
• Base station placement on boundary of a convex polygon
• COMPUTING A DOUBLE-RAY CENTER FOR A PLANAR POINT SET
• Minimum-sum dipolar spanning tree in \(\mathbb R^3\)
• The 2-center problem in three dimensions
• scientific article; zbMATH DE number 970602 (Why is no real title available?)
• Discrete and mixed two-center problems for line segments
• Approximating the discrete center line segment in linear time
• A faster algorithm for the two-center decision problem
• Algorithms for halfplane coverage and related problems
• Optimal algorithm for the planar two-center problem
• Optimal algorithm for the planar two-center problem
• Dominating set, independent set, discrete k-center, dispersion, and related problems for planar points in convex position
• Algorithms for halfplane coverage and related problems
• A fast deterministic smallest enclosing disk approximation algorithm

This page was built for publication: The discrete 2-center problem

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