Partitioning and separating sets of orthogonal polygons

We consider the computation of the orthogonal convex hull of a set of orthogonal simple polygons, where by orthogonal we mean that only horizontal and vertical orientations of edges are allowed. This, as we show, induces a partition of the set of orthogonal polygons. We provide an algorithm to compu...

Full description

Saved in:
Bibliographic Details
Published in:Information sciences 1987-06, Vol.42 (1), p.31-49
Main Authors: Ottmann, Thomas, Soisalon-Soininen, Eljas, Wood, Derick
Format: Article
Language:English
Subjects:
Applied sciences
Artificial intelligence
Computer science
control theory
systems
Exact sciences and technology
Pattern recognition. Digital image processing. Computational geometry
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the computation of the orthogonal convex hull of a set of orthogonal simple polygons, where by orthogonal we mean that only horizontal and vertical orientations of edges are allowed. This, as we show, induces a partition of the set of orthogonal polygons. We provide an algorithm to compute the orthogonal-convex-hull partition of a set of p orthogonal polygons in O( n log p) time and O( n) space, where n is the total number of vertices of the p polygons. Moreover we prove that this is both time and space optimal. For the case p = 1, an O( n) time- and space-optimal algorithm is also presented. We simplify the description of the algorithms by making essential use of a decomposition theorem which we also prove. As we demonstrate, these results enable us to solve a number of separability problems for polygons. In particular, 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.
ISSN:0020-0255
1872-6291
DOI:10.1016/0020-0255(87)90014-4