Computing a minimum-width cubic and hypercubic shell

DOI10.1016/j.orl.2019.07.006zbMath1476.90279arXiv1904.06833OpenAlexW2957834469WikidataQ127471234 ScholiaQ127471234MaRDI QIDQ2294346

Sang Won Bae

Publication date: 10 February 2020

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

Full work available at URL: https://arxiv.org/abs/1904.06833

zbMATH Keywords

facility locationgeometric optimizationexact algorithmminimum widthcubic shellhypercubic shell

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Cites Work

• The geodesic diameter of polygonal domains
• Minimum-width rectangular annulus
• Finding the upper envelope of n line segments in O(n log n) time
• An optimal \(O(n\log n)\) algorithm for finding an enclosing planar rectilinear annulus of minimum width
• The upper envelope of piecewise linear functions: Algorithms and applications
• Establishment of a pair of concentric circles with the minimum radial separation for assessing roundness error
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions
• Approximation algorithms for minimum-width annuli and shells
• Computing a minimum-width square annulus in arbitrary orientation
• Efficient randomized algorithms for some geometric optimization problems
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• Applications of Parametric Searching in Geometric Optimization
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS

This page was built for publication: Computing a minimum-width cubic and hypercubic shell