On the minimum-area rectangular and square annulus problem

DOI10.1016/J.COMGEO.2020.101697MaRDI QIDQ827319zbMATH OpenOpenAlexFDO

Authors Sang Won Bae

Publication date 7 January 2021

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

rectangular annulusminimum areaminimum widtharbitrary orientationsquare annulus

Mathematics Subject Classification ID

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

Abstract: In this paper, we address the minimum-area rectangular and square annulus problem, which asks a rectangular or square annulus of minimum area, either in a fixed orientation or over all orientations, that encloses a set $P$ of $n$ input points in the plane. To our best knowledge, no nontrivial results on the problem have been discussed in the literature, while its minimum-width variants have been intensively studied. For a fixed orientation, we show reductions to well-studied problems: the minimum-width square annulus problem and the largest empty rectangle problem, yielding algorithms of time complexity $O(nlo{g}^{2}n)$ and $O(nlogn)$ for the rectangular and square cases, respectively. In arbitrary orientation, we present $O(n^3)$-time algorithms for the rectangular and square annulus problem by enumerating all maximal empty rectangles over all orientations. The same approach is shown to apply also to the minimum-width square annulus problem and the largest empty square problem over all orientations, resulting in $O(n^3)$-time algorithms for both problems. Consequently, we improve the previously best algorithm for the minimum-width square annulus problem by a factor of logarithm, and present the first algorithm for the largest empty square problem in arbitrary orientation. We also consider bicriteria optimization variants, computing a minimum-width minimum-area or minimum-area minimum-width annulus.

Recommendations

• Minimum-width rectangular annulus
• Computing a minimum-width square annulus in arbitrary orientation
• Minimum Width Rectangular Annulus
• Maximum-width empty square and rectangular annulus
• Computing a Minimum-Width Square Annulus in Arbitrary Orientation

Cites work

• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• A new algorithm for the largest empty rectangle problem
• APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
• 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 extent measures of points.
• Computing a minimum-width square annulus in arbitrary orientation
• Computing a minimum-width square or rectangular annulus with outliers
• Computing the Largest Empty Rectangle
• 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
• Largest empty rectangle among a point set
• Maximum-width empty square and rectangular annulus
• Minimum-width annulus with outliers: circular, square, and rectangular cases
• Minimum-width rectangular annulus
• On the maximum empty rectangle problem
• THE LARGEST EMPTY ANNULUS PROBLEM

Cited in

(12)

• Minimum-width square annulus intersecting polygons
• Computing a minimum-width square or rectangular annulus with outliers
• Computing a minimum-width square annulus in arbitrary orientation
• An optimal algorithm for the minimum-width cubic shell problem
• Maximum-width empty square and rectangular annulus
• scientific article; zbMATH DE number 5356262 (Why is no real title available?)
• Empty squares in arbitrary orientation among points
• Computing a Minimum-Width Square Annulus in Arbitrary Orientation
• Computing a Minimum-Width Square or Rectangular Annulus with Outliers
• Minimum-width rectangular annulus
• Minimum-width annulus with outliers: circular, square, and rectangular cases
• Maximum-width empty square and rectangular annulus

This page was built for publication: On the minimum-area rectangular and square annulus problem

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