Largest empty rectangle
Encyclopedia
In computational geometry
, the largest empty rectangle problem, maximal empty rectangle problem or maximum empty rectangle problem, is the problem of finding a rectangle
of maximal size to be placed among obstacles in the plane. There are a number of variants of the problem, depending on the particularities of this generic formulation, in particular, depending on the measure of the "size", domain (type of obstacles), and the orientation of the rectangle.
The problems of this kind arise e.g., in electronic design automation
, in design and verification of physical layout of integrated circuit
s.
A maximal empty rectangle (MER) is a rectangle which is not contained in another empty rectangle. Each side of a MER abuts an obstacle (otherwise the side may be shifted outwards, increasing the empty rectangle). An application of this kind is enumeration of "maximal white rectangles" in image segmentation R&D of image processing
and pattern recognition
. In the contexts of many algorithms for largest empty rectangles, "maximal empty rectangles" are candidate solutions to be considered by the algorithm, since it is easily proven that, e.g., a maximum-area empty rectangle is a maximal empty rectangle.
Another major classification is whether the rectangle is sought among axis-oriented or arbitrarily oriented rectangles.
s in
metrics for the corresponding obstacle set, similarly to the largest empty circle problem. In particular, for the case of points within rectangle an optimal algorithm of time complexity
is known.
, where s is the number of feasible solutions, i.e., maximal empty rectangles. They also proved that 
and gave an example in which s is quadratic in n. Afterwards a number of papers presented better algorithms for the problem.
line segments was first considered in 1990. Later a more general problem of empty isothetic rectangles among non-isothetic obstacles was considered.
problem, as well as for enumeration of all maximal isothetic empty cuboids.
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, the largest empty rectangle problem, maximal empty rectangle problem or maximum empty rectangle problem, is the problem of finding a rectangle
Rectangle
In Euclidean plane geometry, a rectangle is any quadrilateral with four right angles. The term "oblong" is occasionally used to refer to a non-square rectangle...
of maximal size to be placed among obstacles in the plane. There are a number of variants of the problem, depending on the particularities of this generic formulation, in particular, depending on the measure of the "size", domain (type of obstacles), and the orientation of the rectangle.
The problems of this kind arise e.g., in electronic design automation
Electronic design automation
Electronic design automation is a category of software tools for designing electronic systems such as printed circuit boards and integrated circuits...
, in design and verification of physical layout of integrated circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
s.
A maximal empty rectangle (MER) is a rectangle which is not contained in another empty rectangle. Each side of a MER abuts an obstacle (otherwise the side may be shifted outwards, increasing the empty rectangle). An application of this kind is enumeration of "maximal white rectangles" in image segmentation R&D of image processing
Image processing
In electrical engineering and computer science, image processing is any form of signal processing for which the input is an image, such as a photograph or video frame; the output of image processing may be either an image or, a set of characteristics or parameters related to the image...
and pattern recognition
Pattern recognition
In machine learning, pattern recognition is the assignment of some sort of output value to a given input value , according to some specific algorithm. An example of pattern recognition is classification, which attempts to assign each input value to one of a given set of classes...
. In the contexts of many algorithms for largest empty rectangles, "maximal empty rectangles" are candidate solutions to be considered by the algorithm, since it is easily proven that, e.g., a maximum-area empty rectangle is a maximal empty rectangle.
Classification
In terms of size measure, the two most common cases are the largest-area empty rectangle and largest-perimeter empty rectangle.Another major classification is whether the rectangle is sought among axis-oriented or arbitrarily oriented rectangles.
Maximum-area square
The case when the sought rectangle is an axis-oriented square may be treated using Voronoi diagramVoronoi diagram
In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...
s in
metrics for the corresponding obstacle set, similarly to the largest empty circle problem. In particular, for the case of points within rectangle an optimal algorithm of time complexityTime complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
is known. Domain: rectangle containing points
A problem first discused by Naamad, Lee and Hsu in 1983 is stated as follows: given a rectangle A containing n points, find a largest-area rectangle with sides parallel to those of A which lies within A and does not contain any of the given points. Naamad, Lee and Hsu presented an algorithm of time complexityTime complexity
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and...
, where s is the number of feasible solutions, i.e., maximal empty rectangles. They also proved that and gave an example in which s is quadratic in n. Afterwards a number of papers presented better algorithms for the problem.Domain: line segment obstacles
The problem of empty isothetic rectangles among isotheticIsothetic polygon
An isothetic polygon is a polygon whose alternate sides belong to two parametric families of straight lines which are pencils of lines with centers at two points...
line segments was first considered in 1990. Later a more general problem of empty isothetic rectangles among non-isothetic obstacles was considered.
Higher dimensions
In 3-dimensional space, algorithms for finding a largest maximal empty isothetic cuboidCuboid
In geometry, a cuboid is a solid figure bounded by six faces, forming a convex polyhedron. There are two competing definitions of a cuboid in mathematical literature...
problem, as well as for enumeration of all maximal isothetic empty cuboids.