Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles (Q790614): Difference between revisions

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.