Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles

DOI10.1007/BF00264251MaRDI QIDQ790614zbMATH OpenOpenAlexFDO

Authors Ralf Hartmut Gueting

Publication date 1984

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00264251

zbMATH Keywords

computational geometrycontour problemdivide-and-conquer algorithmmeasure problemorthogonal planer objectsrectanglesseparational representation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

We consider two geometrical problems that have been solved previously by linesweep algorithms: the measure problem and the contour problem. Both problems involve determining some property of the union of a set of rectangles, namely the size and the contour (boundary) of the union. We devise essentially a single time-optimal divide-and-conquer algorithm to solve both problems. This can be seen as a step towards comparing the power of the line-sweep and the divide-and-conquer paradigms. The suprisingly efficient divide-and-conquer algorithm is obtained by using a new technique called separational representation, which extends the applicability of divide-and-conquer to orthogonal planer objects.

Recommendations

• scientific article; zbMATH DE number 3846893
• Divide-and-conquer in planar geometry
• An optimal contour algorithm for iso-oriented rectangles
• The contour problem for rectilinear polygons
• Time-and space-optimal contour computation for a set of rectangles

Cites work

• Algorithms for Reporting and Counting Geometric Intersections
• An optimal contour algorithm for iso-oriented rectangles
• Finding Rectangle Intersections by Divide-and-Conquer
• Finding the contour of a union of iso-oriented rectangies
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Optimal algorithms to compute the closure of a set of iso-rectangles

Cited in

(11)

• A practical divide-and-conquer algorithm for the rectangle intersection problem
• Time-and space-optimal contour computation for a set of rectangles
• A faster optimal algorithm for the measure problem
• Parallel computational geometry of rectangles
• On the parallel-decomposability of geometric problems
• Internal and external algorithms for the point-in-regions problem - the INSIDE join of georelational algebra
• scientific article; zbMATH DE number 3846893 (Why is no real title available?)
• Finding Rectangle Intersections by Divide-and-Conquer
• An optimal contour algorithm for iso-oriented rectangles
• Divide-and-conquer in planar geometry
• The contour problem for rectilinear polygons

This page was built for publication: Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles

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