Minimum-width double-strip and parallelogram annulus

DOI10.1016/J.TCS.2020.05.045MaRDI QIDQ784485zbMATH OpenOpenAlexFDO

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, https://drops.dagstuhl.de/opus/volltexte/2019/11521/

zbMATH Keywords

arbitrary orientationcomputational geometrydouble-stripexact algorithmgeometric 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.

Review text

A planar strip is the closed set of points between two parallel lines, and its width is the (orthogonal) distance between these lines. A double strip is the closure of the difference of an outer strip and an included inner strip, its width being half the difference between both strips' widths. A parallelogram annulus is obtained from two double strips of different orientations by intersecting their outer strips and deleting the interior of the intersected inner strips, its width being the larger of both double strip widths. Given a set of \(n\) points \(P\) in the plane and a subset \(Q\) of size \(k\), a minimum-width double strip containing \(Q\) with outer strip containing \(P\) can be computed in \(O(n\log n+kn)\) time using the geometric dual. With a same complexity one may compute such a minimum-width double strip for all stepwise reduced \(Q\) in prespecified order. A minimum-width parallelogram annulus containing \(P\) is computable in \(O(n)\) time for two fixed orientations, in \(O(n^2)\) time for a single fixed orientation, and in \(O(n^3\log n)\) time when both orientations are free.

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

• 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
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• 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

(9)

• The strip of minimum width covering a centrally symmetric set of points
• Minimum Width Rectangular Annulus
• scientific article; zbMATH DE number 4184294 (Why is no real title available?)
• Minimum-width double-slabs and widest empty slabs in high dimensions
• An optimal algorithm for the minimum-width cubic shell problem
• Parallel line centers with guaranteed separation
• Minimum-width double-slabs and widest empty slabs in high dimensions
• Constrained two-line center problems
• 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)