Minimum-width double-strip and parallelogram annulus

DOI10.1016/J.TCS.2020.05.045zbMATH Open1455.68228OpenAlexW2991015355MaRDI QIDQ784485FDOQ784485

Authors Sang Won Bae

Publication date 3 August 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

computational geometryexact algorithmarbitrary orientationdouble-stripgeometric dualparallelogram annulustwo-line center

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: In this paper, we study the problem of computing a minimum-width double-strip or parallelogram annulus that encloses a given set of $n$ points in the plane. A double-strip is a closed region in the plane whose boundary consists of four parallel lines and a parallelogram annulus is a closed region between two edge-parallel parallelograms. We present several first algorithms for these problems. Among them are $O(n^2)$ and $O(n^{3}logn)$-time algorithms that compute a minimum-width double-strip and parallelogram annulus, respectively, when their orientations can be freely chosen.

Recommendations

• Minimum-width rectangular annulus
• Minimum Width Rectangular Annulus
• Computing a minimum-width square annulus in arbitrary orientation
• Minimum-width annulus with outliers: circular, square, and rectangular cases
• An optimal \(O(n\log n)\) algorithm for finding an enclosing planar rectilinear annulus of minimum width

Cites work

• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• An optimal \(O(n\log n)\) algorithm for finding an enclosing planar rectilinear annulus of minimum width
• Applications of Parametric Searching in Geometric Optimization
• 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
• On some geometric selection and optimization problems via sorted matrices
• The two-line center problem from a polar view: a new algorithm and data structure

Cited in

(5)

• The strip of minimum width covering a centrally symmetric set of points
• An optimal algorithm for the minimum-width cubic shell problem
• Minimum-width double-slabs and widest empty slabs in high dimensions
• Minimum Width Rectangular Annulus
• An optimal \(O(n\log n)\) algorithm for finding an enclosing planar rectilinear annulus of minimum width

This page was built for publication: Minimum-width double-strip and parallelogram annulus

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