Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles (Q790614)
From MaRDI portal
![]() | This is a page for a Wikibase entity. It is used by other Wikibase pages, but it is generally not meant to be viewed directly. See Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles for the user view. |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles |
scientific article |
Statements
Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles (English)
0 references
1984
0 references
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.
0 references
computational geometry
0 references
measure problem
0 references
contour problem
0 references
rectangles
0 references
divide-and-conquer algorithm
0 references
separational representation
0 references
orthogonal planer objects
0 references