2018/11/15 by Bae, Sang Won, Baral, Arpita, Mahapatra, Priya Ranjan Sinha
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1811.06217
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(n3) and O(n2 log n) time for computing a maximum-width empty axis-parallel square and rectangular annulus, respectively. Both algorithms use only O(n) space.