Parametric Algorithm to Find the Largest Empty Rectangle from a Set of Line Segments

A combinatorial algorithm to locate the Maximum Empty Rectangle ([Formula: see text]) inside a given set [Formula: see text] of non-intersecting horizontal and vertical line segments is presented in this paper. The [Formula: see text] is the maximum area rectangle such that no line segment lies in part or in full within the rectangle. The proposed algorithm uses the projection lists and line sweep technique [Formula: see text], where [Formula: see text] is the cardinality of the set [Formula: see text], and [Formula: see text] is the maximum number of candidate rectangles for a line segment. Projection list is the projection of the line segments on [Formula: see text] and [Formula: see text] axes.