Maximum-width empty square and rectangular annulus

DOI10.1007/978-3-030-10564-8_6MaRDI QIDQ5919657zbMATH OpenOpenAlexFDO

Authors Sang Won Bae, Arpita Baral, Priya Ranjan Sinha Mahapatra

Publication date 15 October 2019

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40) Discrete location and assignment (90B80)

Abstract: An annulus is, informally, a ring-shaped region, often described by two concentric circles. The maximum-width empty annulus problem asks to find an annulus of a certain shape with the maximum possible width that avoids a given set of $n$ points in the plane. This problem can also be interpreted as the problem of finding an optimal location of a ring-shaped obnoxious facility among the input points. In this paper, we study square and rectangular variants of the maximum-width empty anuulus problem, and present first nontrivial algorithms. Specifically, our algorithms run in $O(n^3)$ and $O(n^{2}logn)$ time for computing a maximum-width empty axis-parallel square and rectangular annulus, respectively. Both algorithms use only $O(n)$ space.

Recommendations

• Maximum-width empty square and rectangular annulus
• The Largest Empty Annulus Problem
• THE LARGEST EMPTY ANNULUS PROBLEM
• On the minimum-area rectangular and square annulus problem
• Minimum-width rectangular annulus

Cited in

(8)

• Finding the maximum empty axis-parallel rectangular annulus
• Minimum Width Rectangular Annulus
• The Largest Empty Annulus Problem
• Minimum-width annulus with outliers: circular, square, and rectangular cases
• Maximum-width empty square and rectangular annulus
• Maximum-width rainbow-bisecting empty annulus
• On the minimum-area rectangular and square annulus problem
• Largest empty circle centered on a query line

This page was built for publication: Maximum-width empty square and rectangular annulus

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