Space-efficient Algorithms for Empty Space Recognition among a Point Set in 2D and 3D.
Minati De, Subhas Chandra Nandy · 2011
In this paper, we consider the problem of designing in-place algorithms for computing the maximum area empty rectangle of arbitrary orientation among a set of points in 2D, and the maximum volume empty axisparallel cuboid among a set of points in 3D. If n points are given in an array of size n, the worst case time complexity of our proposed algorithms for both the problems is O(n³); both the algorithms use O(1) extra space in addition to the array containing the input points.