On finding an empty staircase polygon of largest area (width) in a planar point-set

This paper presents an algorithm for identifying a maximal empty-staircase-polygon (MESP) of largest area, among a set of <f>n</f> points on a rectangular floor. A staircase polygon is an isothetic polygon bounded by two monotonically rising (falling) staircases. A monotonically rising staircase is a sequence of alternatingly horizontal and vertical line segments from the bottom-left corner of the floor to its top-right corner such that for every pair of points <f>α=(xα,yα)</f> and <f>β=(xβ,yβ)</f> on the staircase, <f>xα&les;xβ</f> implies <f>yα&les;yβ</f>. A monotonically falling staircase can similarly be defined from the bottom-right corner of the floor to its top-left corner. An empty staircase polygon is a MESP if it is not contained in another larger empty staircase polygon. The problem of recognizing the largest MESP is formulated using permutation graph, and a simple <f>O(n3)</f> time algorithm is proposed. Next, based on certain novel geometric properties of the problem, an improved algorithm is developed that identifies the largest MESP in <f>O(n2)</f> time and space. The algorithm can be easily tailored for identifying the widest MESP in a similar environment. The general problem of locating the largest area/width MESP among a set of isothetic polygonal obstacles, can be solved easily. These geometric optimization problems have several applications to VLSI layout design, robot motion planning, to name a few. [Copyright &y& Elsevier]