Computing a minimum-width cubic and hypercubic shell

DOI10.1016/J.ORL.2019.07.006MaRDI QIDQ2294346zbMATH OpenOpenAlexWikidataFDO

Authors 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

cubic shellexact algorithmfacility locationgeometric optimizationhypercubic shellminimum width

Mathematics Subject Classification ID

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

Abstract: In this paper, we study the problem of computing a minimum-width axis-aligned cubic shell that encloses a given set of $n$ points in a three-dimensional space. A cubic shell is a closed volume between two concentric and face-parallel cubes. Prior to this work, there was no known algorithm for this problem in the literature. We present the first nontrivial algorithm whose running time is $O(nlo{g}^{2}n)$. Our approach easily extends to higher dimension, resulting in an $O(n^{lfloord/2floor}lo{g}^{d-1}n)$-time algorithm for the hypercubic shell problem in $dgeq3$ dimension.

Recommendations

• Exact and approximation algorithms for minimum-width cylindrical shells
• Publication:4952660
• Computing minimum-volume enclosing ellipsoids
• Computing minimum-volume enclosing axis-aligned ellipsoids
• Computation of Minimum-Volume Covering Ellipsoids
• scientific article; zbMATH DE number 5052286
• Approximation algorithms for minimum-width annuli and shells
• Computing a minimum-width square annulus in arbitrary orientation
• Computing minimum-area rectilinear convex hull and L-shape

Cites work

• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• An optimal \(O(n\log n)\) algorithm for finding an enclosing planar rectilinear annulus of minimum width
• Applications of Parametric Searching in Geometric Optimization
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• 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
• Establishment of a pair of concentric circles with the minimum radial separation for assessing roundness error
• Finding the upper envelope of n line segments in O(n log n) time
• Minimum-width rectangular annulus
• The geodesic diameter of polygonal domains
• The upper envelope of piecewise linear functions: Algorithms and applications
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoi diagrams in higher dimensions under certain polyhedral distance functions
• Voronoui Diagrams in L₁ (L_\infty ) Metrics with 2-Dimensional Storage Applications

Cited in

(4)

• Finding minimal enclosing boxes
• scientific article; zbMATH DE number 1445343 (Why is no real title available?)
• Exact and approximation algorithms for minimum-width cylindrical shells
• An optimal algorithm for the minimum-width cubic shell problem

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

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