On finding an empty staircase polygon of largest area (width) in a planar point-set (Q1405008)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On finding an empty staircase polygon of largest area (width) in a planar point-set |
scientific article |
Statements
On finding an empty staircase polygon of largest area (width) in a planar point-set (English)
0 references
25 August 2003
0 references
The problem of recognizing the maximal empty-staircase-polygon of largest area among a set of given points on a rectangular floor (relevant to robot motion planning and VLSI layout design) is formulated using permutation graph. The searched polygon corresponds to a path between two designed nodes in a weighted digraph obtained from the permutation graph. An algorithm is described that computes the searched polygon as the maximum weighted path in the graph. It is observed also that if the edges in the graph are processed in a particular order, then the time complexity can be reduced by exploiting certain geometric properties.
0 references
geometric optimization problem
0 references
algorithm complexity
0 references
permutation graph
0 references
empty-staircase-polygon of largest area planning
0 references
VLSI layout design
0 references
algorithm
0 references
