The contour problem for rectilinear polygons
type: Item
instance of: scholarly article
title: The contour problem for rectilinear polygons
zbMATH Open document ID: 0558.68059
DOI: 10.1016/0020-0190(84)90058-9
published in: Information Processing Letters
publication date: 1984-01-01T00:00:00Z
review text: This paper presents yet another algorithm to solve the contour problem for the union of a set of rectangles or orthogonal polygons. The algorithm is both time- and space-optimal, requiring O(n log n\(+e)\) time and O(n) space, if the input has a total of n vertices and the output has a total of e vertices. The only other algorithm with this performance is the one due to Güting. However his algorithm relies on a complex data structure while the algorithm given here uses a simple variation on the segment tree. Indeed when the input consists solely of rectangles the solution is almost as simple as the original and non-optimal Lipski and Preparata algorithm.
Mathematics Subject Classification ID: 68R99
zbMATH DE Number: 3890751
zbMATH Keywords: optimal algorithm
zbMATH Keywords: sweep plane
zbMATH Keywords: scan line
zbMATH Keywords: disjoint-set union
zbMATH Keywords: contour problem
zbMATH Keywords: rectangles
zbMATH Keywords: orthogonal polygons
zbMATH Keywords: segment tree
author: D. Wood
MaRDI profile type: Publication
full work available at URL: 0020-0190(84)90058-9
OpenAlex ID: W2005465277
cites work: An optimal contour algorithm for iso-oriented rectangles
cites work: Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles
cites work: Finding the contour of a union of iso-oriented rectangies
cites work: On the X-Y convex hull of a set of X-Y polygons
cites work: Q3959475
description: scientific article; zbMATH DE number 3890751