Partitioning and separating sets of orthogonal polygons (Q1097030)

A geometrical object in the plane is said to be orthogonal if its edges are either vertical or horizontal. A polygon is called orthoconvex if for every vertical-or-horizontal segment, its two endpoints lying in the polygon implies the whole segment lying in the polygon. An orthoconvex hull of a collection of polygons is the smallest orthoconvex point set containing the given polygons. It induces a disjoint partition on the collection of polygons, which is called the orthoconvex-hull partition: Two polygons belong to the same component of the partition iff they are contained in the same connected component of the orthoconvex hull. The authors provide an algorithm to compute the orthoconvex-hull partition of a collection of polygons in O(n log(p)) time and O(n) space, where n is the total number of vertices of the p polygons. Moreover, they prove that this is both time and space optimal. To simplify the description of the algorithm, a decomposition theorem is proved. These results enable the authors to solve a number of separability problems for polygons. In particular, they show that the group 4-way isoseparability of p polygons with a total of n vertices can be solved in O(n log(p)) time and O(n) space.