On the maximum empty hyper-rectangle problem
Rewayda Razaq Abo-Alsabeh, Hajem Ati Daham, Abdellah Salhi · Journal of Algorithms & Computational Technology · 2023
Given a rectangle [Formula: see text] containing points, we consider the problem of detecting the largest rectangle that is totally contained in [Formula: see text] and does not include any of the points. In other words, we want to find the biggest hole in the dataset that can contain the biggest possible rectangle. A new algorithm for dealing with this problem is, therefore, suggested. Existing algorithms are exact but cannot deal efficiently with problems in high dimensions and large instances. In fact, only computing maximum empty rectangles in a set of points in [Formula: see text] has been well addressed. In high dimensions, the problem is shown to be NP-complete. Our suggested approach is evolutionary in nature and is an innovative implementation of the genetic algorithm. The approach solves a more general form of the stated problem in that it ignores the axis-parallel condition imposed on the hyper-rectangles to be found. This paper includes computational results and their discussions.