The contour problem for rectilinear polygons

DOI10.1016/0020-0190(84)90058-9MaRDI QIDQ802313zbMATH OpenOpenAlexFDO

Authors D. Wood

Publication date 1984

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(84)90058-9

zbMATH Keywords

contour problemdisjoint-set unionoptimal algorithmorthogonal polygonsrectanglesscan linesegment treesweep plane

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

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.

Recommendations

• Time-and space-optimal contour computation for a set of rectangles
• An optimal contour algorithm for iso-oriented rectangles
• scientific article; zbMATH DE number 3846893
• Hole Problems for Rectangles in the Plane
• Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles

Cites work

• An optimal contour algorithm for iso-oriented rectangles
• Finding the contour of a union of iso-oriented rectangies
• scientific article; zbMATH DE number 3780616 (Why is no real title available?)
• On the X-Y convex hull of a set of X-Y polygons
• Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles

Cited in

(17)

• Time-and space-optimal contour computation for a set of rectangles
• Systolic algorithms for rectilinear polygons
• Sweep methods for parallel computational geometry
• An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented rectangles
• A fast algorithm for an envelope construction of a huge set of topologically consistent polygons
• The Hausdorff core problem on simple polygons
• scientific article; zbMATH DE number 3846893 (Why is no real title available?)
• An optimal contour algorithm for iso-oriented rectangles
• A fast algorithm for the Boolean masking problem
• Hole Problems for Rectangles in the Plane
• scientific article; zbMATH DE number 1190951 (Why is no real title available?)
• Reassembling polygons from edges
• An application of the Hooley-Huxley contour
• scientific article; zbMATH DE number 3804872 (Why is no real title available?)
• Computational Science and Its Applications – ICCSA 2004
• An output-sensitive algorithm for computing the union of cubes and fat boxes in 3D
• Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles

This page was built for publication: The contour problem for rectilinear polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q802313)