2020 | OriginalPaper | Chapter
Finding the Maximum Empty Axis-Parallel Rectangular Annulus
Authors: Raina Paul, Apurba Sarkar, Arindam Biswas
Publisher: Springer International Publishing
Published in:
Combinatorial Image Analysis
Abstract
An annulus is basically a ring-shaped region between two concentric disks on the same plane. However, it can be defined on any other geometrical shapes, for example, a rectangular annulus is defined as the area between two rectangles with one rectangle enclosing the other. The area of the annulus is the area of the region between the two shapes. An axis-parallel rectangular annulus is an annulus where the sides of the rectangles are parallel to the co-ordinate axes. This paper presents a combinatorial technique to find the largest empty axis-parallel rectangular annulus from a given set of n points and runs in \(O(n\log n)\) time. It uses two balanced binary search trees to store the points and reduces the complexity of the existing algorithm in the literature.
