Minimum-width double-strip and parallelogram annulus

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

Authors: Sang Won Bae 

Publication date: 3 August 2020

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Finding the upper envelope of n line segments in O(n log n) time
• Establishment of a pair of concentric circles with the minimum radial separation for assessing roundness error
• Efficient randomized algorithms for some geometric optimization problems
• Minimum-width rectangular annulus
• Applications of Parametric Searching in Geometric Optimization
• An optimal \(O(n\log n)\) algorithm for finding an enclosing planar rectilinear annulus of minimum width
• On some geometric selection and optimization problems via sorted matrices
• Computing a minimum-width square annulus in arbitrary orientation
• The two-line center problem from a polar view: a new algorithm and data structure

Cited In (6)

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

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)