An optimal O(n n) algorithm for finding an enclosing planar rectilinear annulus of minimum width

DOI10.1016/J.ORL.2009.02.007zbMATH Open1167.90629OpenAlexW1586057350MaRDI QIDQ833568FDOQ833568

Horst W. Hamacher, Arie Tamir, Olga N. Gluchshenko

Publication date: 14 August 2009

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2009.02.007

Recommendations

• Minimum-width rectangular annulus
• Minimum Width Rectangular Annulus
• Computing a minimum-width square annulus in arbitrary orientation
• Computing a Minimum-Width Square Annulus in Arbitrary Orientation
• Minimum-width double-strip and parallelogram annulus

zbMATH Keywords

facility locationoptimal algorithmminimum width annulusplanar locationrectilinear annulus

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximating extent measures of points
• Equity measurement in facility location analysis: A review and framework
• Equity models in planar location
• Improved algorithms for several network location problems with equality measures.
• Efficient randomized algorithms for some geometric optimization problems
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• Extensive facility location problems on networks with equity measures

Cited In (18)

• An optimal algorithm for the minimum-width cubic shell problem
• Minimum-width annulus with outliers: circular, square, and rectangular cases
• On the minimum-area rectangular and square annulus problem
• Maximum-width empty square and rectangular annulus
• Computing a minimum-width square or rectangular annulus with outliers
• Minimum width color spanning annulus
• Empty squares in arbitrary orientation among points
• Computing a Minimum-Width Square Annulus in Arbitrary Orientation
• Computing a Minimum-Width Square or Rectangular Annulus with Outliers
• Minimum Width Color Spanning Annulus
• Minimum Width Rectangular Annulus
• Locating an axis-parallel rectangle on a Manhattan plane
• Computing a minimum-width cubic and hypercubic shell
• Minimum-width double-strip and parallelogram annulus
• Locating a minisum annulus: a new partial coverage distance model
• Red-blue rectangular annulus cover problem
• Computing a minimum-width square annulus in arbitrary orientation
• Minimum-width rectangular annulus

This page was built for publication: An optimal \(O(n\log n)\) algorithm for finding an enclosing planar rectilinear annulus of minimum width

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