A (1+)-approximation algorithm for 2-line-center

DOI10.1016/S0925-7721(03)00017-8MaRDI QIDQ1405006zbMATH OpenFDO

Authors Cecilia M. Procopiuc, Kasturi Varadarajan, Pankaj K. Agarwal

Publication date 25 August 2003

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0925-7721(03)00017-8

zbMATH Keywords

2-line-center problemapproximation algorithmsprojective clusteringshape fitting

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Review text

Given a set \(S\) of \(n\) points in \(\mathbb R^2\), the two-line center problem consists of finding two strips covering \(S\) such that the maximum width of the strips is minimized. Known algorithms giving the exact solution require run times that grow almost like \(n^2\). In the paper under review, an approximation algorithm is presented that gives a nearly optimal solution with strip width \((1+\varepsilon)w^*\) instead of \(w^*\). The run time of this algorithm is only \(O(n (\log n + \varepsilon^{-2} \log \varepsilon^{-1}) + \varepsilon^{-7/2} \log\varepsilon^{-1})\).

Recommendations

• The two-line center problem from a polar view: a new algorithm and data structure
• Approximation algorithms for orthogonal line centers
• scientific article; zbMATH DE number 1947381
• A near-linear algorithm for the planar 2-center problem
• The discrete 2-center problem

Cites work

• Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus
• Computing the width of a set
• Efficient randomized algorithms for some geometric optimization problems
• Geometric complexity of some location problems
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 741008 (Why is no real title available?)
• scientific article; zbMATH DE number 1947381 (Why is no real title available?)
• scientific article; zbMATH DE number 1559577 (Why is no real title available?)
• scientific article; zbMATH DE number 1445346 (Why is no real title available?)
• scientific article; zbMATH DE number 6472585 (Why is no real title available?)
• On some geometric selection and optimization problems via sorted matrices
• On the complexity of locating linear facilities in the plane
• The two-line center problem from a polar view: a new algorithm and data structure

Cited in

(11)

• A near-linear algorithm for the planar 2-center problem
• Approximating k-orthogonal line center
• scientific article; zbMATH DE number 1947381 (Why is no real title available?)
• APPROXIMATING 3D POINTS WITH CYLINDRICAL SEGMENTS
• The two-line center problem from a polar view: a new algorithm and data structure
• Analysis of incomplete data and an intrinsic-dimension Helly theorem
• Approximation algorithms for orthogonal line centers
• Parallel line centers with guaranteed separation
• Constrained two-line center problems
• Approximation algorithms for a \(k\)-line center
• Approximation algorithms for orthogonal line centers

This page was built for publication: A (\(1+{\varepsilon}\))-approximation algorithm for 2-line-center

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