Time-and space-optimal contour computation for a set of rectangles

DOI10.1016/0020-0190(87)90159-1MaRDI QIDQ1108000zbMATH OpenOpenAlexFDO

Authors Peter Widmayer, D. Wood

Publication date 1987

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

Full work available at URL https://doi.org/10.1016/0020-0190(87)90159-1

zbMATH Keywords

computational geometryoptimal contour computation

Mathematics Subject Classification ID

Other problems of combinatorial convexity (52A37) Analysis of algorithms and problem complexity (68Q25)

Review text

We present the first time- and space-optimal algorithm for the problem of computing the contours of the disjoint polygons defined by the union of n rectangles in the plane. It requires O(n log n\(+e)\) time and O(n) space, where e is the total number of edges in the contour cycles. The space optimality of the solution is demonstrated by way of a combinatorial argument.

Recommendations

• An optimal contour algorithm for iso-oriented rectangles
• The contour problem for rectilinear polygons
• scientific article; zbMATH DE number 3846893
• Hole Problems for Rectangles in the Plane
• An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented 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 3907794 (Why is no real title available?)
• Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles
• Plane-sweep algorithms for intersecting geometric figures
• The contour problem for rectilinear polygons

Cited in

(14)

• Sweep methods for parallel computational geometry
• An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented rectangles
• Data filtering based least squares iterative algorithm for parameter identification of output error autoregressive systems
• scientific article; zbMATH DE number 3846893 (Why is no real title available?)
• An optimal time and minimal space algorithm for rectangle intersection problems
• Optimal algorithms to compute the closure of a set of iso-rectangles
• An optimal contour algorithm for iso-oriented rectangles
• Two Linear-Time Algorithms for Computing the Minimum Length Polygon of a Digital Contour
• Hole Problems for Rectangles in the Plane
• scientific article; zbMATH DE number 3804872 (Why is no real title available?)
• Space-optimal hidden line elimination for rectangles
• Two linear-time algorithms for computing the minimum length polygon of a digital contour
• Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles
• The contour problem for rectilinear polygons

This page was built for publication: Time-and space-optimal contour computation for a set of rectangles

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