Hole Problems for Rectangles in the Plane

DOI10.1137/0401010MaRDI QIDQ3779343zbMATH OpenOpenAlexFDO

Authors Gregory J. E. Rawlins, Peter Widmayer, D. Wood

Publication date 1988

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0401010

zbMATH Keywords

countingholesreportingspace- optimal algorithmstime-optimal algorithmsunion of rectangles

Mathematics Subject Classification ID

Designs and configurations (05B99) Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Recommendations

• The contour problem for rectilinear polygons
• Time-and space-optimal contour computation for a set of rectangles
• scientific article; zbMATH DE number 3804872
• An optimal contour algorithm for iso-oriented rectangles
• Efficient algorithms for the largest rectangle problem

Cited in

(8)

• Time-and space-optimal contour computation for a set of rectangles
• An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented rectangles
• An optimal time and minimal space algorithm for rectangle intersection problems
• Hierarchical representations of collections of small rectangles
• scientific article; zbMATH DE number 219276 (Why is no real title available?)
• scientific article; zbMATH DE number 3804872 (Why is no real title available?)
• A parallel algorithm to construct a dominance graph on nonoverlapping rectangles
• The contour problem for rectilinear polygons

This page was built for publication: Hole Problems for Rectangles in the Plane

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