Acta Informatica 21,271-291 (1984)

9 Springer-Verlag 1984

Optimal Divide-and-Conquer to Compute Measure

and Contour for a Set of Iso-Rectangles*

Ralf Hartmut Giiting

Lehrstuhl Informatik VI, Universitiit Dortmund, D-4600 Dortmund 50 (Fed. Rep.)

Summary. We reconsider two geometrical problems that have been solved

previously by line-sweep 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 algo-
rithm to solve both problems. This can be seen as a step towards compar-
ing the power of the line-sweep and the divide-and-conquer paradigms. The
surprisingly efficient divide-and-conquer algorithm is obtained by using a
new technique called "separational representation", which extends the ap-
plicability of divide-and-conquer to orthogonal planar objects.

1. Introduction

Over the last few years much attention has been paid to problems based on a
set of iso-oriented rectangles. (A set of rectangles is iso-oriented if the sides of
all rectangles are parallel to the coordinate axes). The problems studied include
finding all intersecting pairs in a set of rectangles [5, 7, 13], computing the
measure of the union, constructing the contour of the union, finding connected
components [8] and computing the closure of a set of rectangles [16].
The interest in these problems is due to the fact that sets of rectangles play
an important role in VLSI-design (see for instance [14]) and that they have
other applications as well, e.g. in geography [4], in maintaining architectural
data bases [6], and in computer graphics.
In almost all cases these problems have been solved by the use of line-sweep
algorithms. The line-sweep paradigm was apparently introduced into com-
putational geometry by Shamos and Hoey [15] and afterwards widely used to
solve problems based on a set of objects in the plane. The idea is to move a

* This work was partially supported by the DAAD (Deutscher Akademischer Austauschdienst)
and by the DFG (Deutsche Forschungsgemeinschaft)
272 R.H. Gfiting

(say) vertical line from left to right through the set of objects. At any position
the sweepline may intersect some of the objects which are represented by their
projection onto the sweepline. The problem is solved by observing the in-
teraction between the projected objects.
Until recently, line-sweep seemed to be the only way to solve problems
based on sets of planar objects efficiently. In [11] Giiting and Wood showed
that the same efficiency can be obtained by using the well-known algorithmic
paradigm of divide-and-conquer. There, a time- and space-optimal algorithm for
the rectangle intersection problem is given. They key idea that makes efficient
divide-and-conquer possible is called separational representation (of planar ob-
jects). In this paper we use the same technique to solve two other problems
based on a set of rectangles. Both problems concern "free" and "covered"
areas of the plane. (A point of the plane is called covered with respect to a set
of rectangles R if there exists a rectangle in R containing it. Otherwise it is
called J~'ee with respect to R. This definition extends in the obvious way to a
set of intervals in 1-space).

The Measure Problem

Given a set of n iso-oriented rectangles in the plane, determine the measure of

their union.
In other words we ask for the size of the covered area of the plane. This
problem was solved by Bentley [2] by means of a line-sweep algorithm in
optimal - i.e. O(n logn) - time.

The Contour Problem

For a set of iso-oriented rectangles in the plane, the contour is the boundary
between the free and the covered area of the plane. In general it is a collection
of disjoint "contour cycles", each of which is a sequence of alternating hori-
zontal and vertical contour pieces.

Fig. 1

The contour problem is to construct this collection of contour cycles. It was

posed and first attacked by Lipski and Preparata [12 3. They used a line-sweep
algorithm with a segment tree as a supporting data structure to obtain an
Computing Measure and Contour by Divide-and-Conquer 273

O(n log n + p log (2n2/p)) - time solution where n is the number of rectangles and
p the number of contour pieces. Only recently a time-optimal, that is O (n log n + p)
- time, solution was found by Gating [9]. Again a line-sweep algorithm
was used, supported by a rather sophisticated data structure called a con-
tracted segment tree.
In the sequel we use divide-and-conquer based on separational representa-
tion to develop time-optimal solutions for both problems. Apart from solving
the specific problems our goal is to demonstrate:
1) That divide-and-conquer is a reasonable method to solve problems based
on a set of planar objects.
2) How it is to be applied, namely, using separational representation.
Using a relatively abstract level of description we are able to provide the
essential part of the solution of both problems in a single high-level algorithm.
The paper is structured as follows: In Sect. 2 we reduce both problems to
obtaining a solution from some given abstract description (called siripes) of the
union of the rectangles. In Sect. 3 we give a divide-and-conquer algorithm
STRIPES to compute this description. In Sect. 4 we show how to represent the
description stripes and implement the abstract operations of algorithm
STRIPES, and also analyze time- and space-requirements.

2. R e d u c i n g the P r o b l e m s

At first glance the measure problem and the contour problem may appear
rather different. However, both the measure and the contour are properties of
the union of a set of rectangles. We exploit this fact by developing an abstract
description of this union which makes the solution of both the measure and
the contour problem relatively easy. Hence our approach has two steps: First,
compute the description stripes of a set of rectangles using the divide-and-
conquer algorithm STRIPES. Second, given stripes, solve the specific problem.
Since the second step is relatively simple for both problems, it is essentially the
one powerful algorithm STRIPES that solves both problems.
It must be noted, however, that the "abstract data structure" stripes is
identical for both problems only on a high level of abstraction. When it comes
to implementation we have to use different representations of stripes for the
two problems to obtain efficient solutions. Thus in Sect. 4 a specialization of
data structure stripes and algorithm STRIPES is introduced.
Let R be the given set of rectangles with cardinality n. At present we
assume for simplicity the x- and y-coordinates of all rectangles to be pairwise
distinct, that is, R defines 2n different x-coordinates and 2n different y-coor-
dinates. This restriction is removed in Sect. 4. The description of R we choose
is a partition of the plane into horizontal stripes. For technical reasons we
want to exclude infinite stripes, hence we first choose arbitrarily a rectangular
"frame" f completely enclosing the given set of rectangles. The area of this
frame is then divided into horizontal rectangular stripes. This partition is
imposed by the horizontal edges of rectangles in R, that is, each edge coincides
with a stripe's boundary and each (internal) stripe's boundary coincides with a
horizontal edge:
274 R.H. Gating

I I
Fig. 2

N o t e that the part of the union of the rectangles in R that falls into any
particular stripe is completely defined by a set of disjoint x-intervals.
To formalize the collection of stripes and to be able to describe operations
on it we need a few data type and function definitions. We use an algorithmic
design n o t a t i o n to describe functions in the mathematical and in the com-
putational sense in a uniform manner. Thus some of the constructs below serve
for specification and cannot be implemented directly (since, for instance, they
deal with infinite sets of objects).
type coord = I! u { - o% + oo }
type point = (eoord x, coord y)
type interval = (eoord bottom, eoord top)
type line_segment =(interval int, coord coord)
type rectangle = (coord x _ left, coord x _ right, coord y _ bottom,
coord y_ top)
I(interval x_ interval, interval y_ interval)
(rectangle is a variant type, the alternatives are separated by "[")
type edge = (interval int, coord coord, edgetype side)
type edgetype= atomic {left, right, bottom, top}
type stripe = (interval x interval, interval y_ interval, set of interval x_
union).
The only unusual object type is stripe. A stripe consists of a rectangular area
defined by x interval and y_ interval and of a c o m p o n e n t x _ union able to hold
a set of intervals, which is used to represent the part of the union of the
rectangles in R that falls into the stripe's area. The following definitions serve
to specify the particular set of stripes defined by a given set of rectangles R.
Since a rectangle defines a set of points we m a y apply set operations to
rectangles, union (R) defines the area of the plane covered with respect to R:
function union (set of rectangle R) set of point : [9 r
rER

y_set(R) is used below to define the partition of the plane induced by R:

Computing Measure and Contour by Divide-and-Conquer 275

function y_ set (set of rectangle R) set of coord:

{y6coord[3r~R: y = r . y bottom or
y = r . y _ top}
function partition (set of coord Y) set of interval:
{[yl,y2]lyl,Y2EY and Yl <Y2 and
(VyEY: Y--<Ya or Y-->Y2)}
Furthermore we need
function x proj (set of point) set of coord: ...
to project a set of points onto the x-axis. If we apply x proj to a connected
region of the plane we would like to interpret the result as an interval rather
than a set of coordinates and therefore define a "type conversion" function
function intervals (set of cord) set of interval: ...
which performs just that transformation. N o w we are able to define the set of
stripes:
function stripes (set of rectangle R, rectangle f:
(V y e y _ set (R): f . y_ bottom < y < f . y _ top)) set of stripe:
set of coord Y: = y_ s e t ( R ) u { f . y_ bottom, f . y_ top} ;
{(i=, iy, i_ set) [ ix = f . x _ interval and
iyepartition (Y) and
i_ set = intervals ( x _ proj((ix, iy) nunion(R)))}

The algorithm S T R I P E S of Sect. 3 computes stripes ( R , f ) for a frame f

completely enclosing R, such that measure and contour can be computed from
this description. Note that the definition is still valid if the x _ interval of f does
not contain the whole x-extension of R, like in Fig. 3:

Ill
ly 2

iY 1

; i B
ix X
: f,x i n t e r v a t

Fig. 3

Sets of stripes of this kind appear as intermediate results of the divide-and-

conquer algorithm S T R I P E S .
To provide some motivation we now show that given a set of stripes the
measure problem and the contour problem can be solved easily.
276 R.H. Giiting

The Measure Problem

Given a set of rectangles R our task is to compute measure(R). First we choose

a frame f completely enclosing and not intersecting any of the rectangles in R.
We then compute S = s t r i p e s ( R , f ) by the divide-and-conquer algorithm
S T R I P E S given in the next section. Now each stripe s in S contains a set of
disjoint intervals s . x _ u n i o n . The only property of s. x u n i o n relevant to the
measure problem is the total length of the contained intervals, that is
measure(s, x union). Then the measure of union(R) is given by

function measure (set of stripe S) real:

(measure(s . x _ union) * (s . y _ interval, top - s . y_ interval, bottom))
sES

The Contour Problem

Recall that for a set of iso-oriented rectangles R the contour is a collection of

contour cycles. Each contour cycle is a sequence of alternating horizontal and
vertical contour pieces. Every contour piece is a fragment of a rectangle edge
from R.
Lipski and Preparata [12] have shown that it is sufficient to know the
contour pieces oriented in one direction (e.g. the horizontal ones) to construct
the complete contour efficiently. Our algorithm therefore only computes the
horizontal contour pieces from the previously constructed data structure
S = stripes(R,f).
Since any horizontal contour piece is a fragment of some rectangle edge
we consider the set H of horizontal rectangle edges defined by R. By con-
struction of S any edge h ~ H coincides with the boundary between two stripes
in S, with its rectangle either above or below it:

iiiiiiiiiii!ii!igiiiiliJiiiiiiiiiiiiiiii!iiiiiiiiii!iiiiii!ilgiiiiggigiiiiiiii
ii!i i lii! h
Fig. 4

The area within a stripe s free with respect to R is given by the complement of
s . x union (together with s.y_interval). The contour pieces created by h are
formed by the intersection of h with that adjacent stripe which is not covered
by h's rectangle (the stripe below h in Fig. 4). This intersection is completely
defined by h. x _ i n t e r v a l and s. x u n i o n . The contour pieces created by h are
given by:
function contour_ pieces (edge h, set of stripe S) set of line segment :
if h. side = bottom
Computing Measure and Contour by Divide-and-Conquer 277

then select s~S such that s. y_interval, top = h. coord

else select s s S such that s. y_interval, bottom=h, coord
fi;
set of interval J : = intervals(h, x _ i n t e r v a l \
(h . x _ interval~union(s . x _ union)));
{(i, y) 1i~d and y = h. coord}
Here after selecting the stripe not covered by h's rectangle the set J of
x_intervals of contour pieces is formed, union applied to the set of intervals
x_union yields the corresponding set of coordinates (defined analogously to
union for a set of rectangles). Intersecting and forming the complement with
h. x interval we obtain the free (w.r.t. J) subintervals of h. x_interval. Together
with h's y-coordinate this yields the contour pieces created by h.
The whole set of contour pieces is simply contour (H,S) defined by
function contour (set of edge H, set of stripe S) set of line segment:
U contour_pieces(h,S)
h~H

3. Computing the Set of Stripes

We now describe how to compute the set of stripes S = s t r i p e s ( R , f ) . We have

seen that, given S, the measure problem and the contour problem could easily
be solved; hence the following is the crucial part of the algorithms.
To compute S efficiently we use divide-and-conquer. For a set of rectangles
R the obvious way to do this is to choose a (say) vertical line which splits R
into three subsets: the rectangles left and right of it, respectively, and those
intersected by it. We may call the sets LEFT, M I D D L E and RIGHT. In this
approach it seems difficult to treat the interaction between e.g. sets L E F T and
MIDDLE.
Therefore we use separational representation in applying divide-and-conquer
to a set of rectangles. The idea is to represent a rectangle by its left and right
vertical edges which are treated by the algorithm as independent units. Hence
the input for the algorithm is a set of vertical line segments instead of a set of
rectangles. By a vertical line this set can be divided into only two equal-sized
subsets L E F T and R I G H T which can be "conquered" independently.
We now describe in a top-down manner the algorithm which uses sub-
algorithms yet to be defined. We then explain the algorithm together with
describing the subalgorithms. The algorithm consists o f . two parts
RECTANGLE_DAC and S T R I P E S ; the quite simple main algorithm
R E C T A N G L E _ D A C only provides an environment for the recursive divide-
and-conquer algorithm STRIPES.
Algorithm R E C T A N G L E _ D A C (RE CT, S)
Input: set of rectangle R E C T : the x- and y-coordinates of all rectangles in
R E C T are pairwise distinct.
Output: set of stripe S :S =stripes ( R E C T , ( - oo, + o% - oo, + oo))
278 R.H. Giiting

Step 1: Let V R X be the set of left and right vertical rectangle edges defined
by R E C Z
Step 2 S T R I P E S ( V R X , [ - oe, + oe], LEFT, R I G H T , P O I N T S , S)
end of algorithm R E C T A N G L E _ D A C.
(Here L E F T , R I G H T and P O I N T S are result parameters of algorithm
S T R I P E S , which are not used in R E C T A N G L E DAC).
In the following description of algorithm S T R I P E S two new terms occur.
F o r a vertical edge of a rectangle r we call the respective other vertical edge its
partner. F o r a set V of vertical edges rect(V) denotes the set of those rectangles
which are represented in V by at least one edge.
Algorithm S T R I P E S ( V , x ext, L, R, P, S)
Input : set of edge V: a set of vertical rectangle edges.
interval x ext: encloses the x-coordinates of all edges in V.
Output: set of interval L: contains the y-projections of all left edges whose
partner is not in V.
set of interval R: symmetric to L (for right edges).
set of cord P: contains the y-projection of all endpoints of line
segments in V plus the flame boundaries in y-direction, namely - o o
and + oo.
set of stripe S: S = stripes (rect (V), (x_ext, [ - oo, + ~])).
Case 1: V contains only one edge v.
if v. side = left
then L: = {v. y_interval}; R: = 0
else L: = 0; R: = {v. y_ interval}
d;
P: = { - ~ , v . y interval, bottom, v . y_interval, top, + ~ } ;
S: = {(ix, iy, 9) ] ix = x _ e x t and iyepartition(V)} ; (A)
select s eS such that s . y _ i n t e r v a l = v. y_ interval;
if v . side = left
then s . x u n i o n : = {[v. coord, x _ e x t . top]} (B)
else s. x u n i o n : = {[-x e x t . bottom, v. coord]} (c)
fi

Case 2: V contains m o r e than one edge.

Divide: Choose an x-coordinate x m dividing V into two a p p r o x i m a t e l y
equal-sized subsets V1 and V2.
Conquer: S T R I P E S ( V 1 , [x_ ext. bottom, Xm], L1, R1, P1, SO;
S T R I P E S ( V 2, [xm, x e x t . top], L2, R2, P2, $2);
Merge: set of interval L R : = L 1 c~R 2 ;

L: = ( L I \ L R ) w L 2 ;
R: = R I U ( R 2 \ L R ) ;
P:=P1uP2;
Computing Measure and Contour by Divide-and-Conquer 279

set of stripe Szeyr: = copy ($1, P, Ix_ ext. bottom, xm]);

set of stripe S,ight: = copy(S2, P, [Xm, X_ ext. top]);
blacken (Sle it, R 2\ L R );
blacken (Sright, L I \ L R ) ;
S: = concat (S,~yt, Sright, P, x_ ext)
end of algorithm STRIPES.
Let us now look at the algorithm S T R I P E S in detail and define the used
subalgorithms copy, blacken and concat. The task of S T R I P E S is to construct
sets L, R, P and S according to the output specification from a given set of
vertical rectangle edges V. Although we are interested only in the set of stripes
S as a final result, sets L, R and P are needed to support the merge step.
Initially S T R I P E S is called by R E C T A N G L E _ D A C with the complete set
of vertical rectangle edges. All edges are located within a "maximal" frame (a
rectangle) f = ( - 0% + co, - 0% + 00). A vertical line is chosen that splits f into
two smaller subframes f l and f2 and V into two subsets V1 and V2 of
approximately equal size enclosed by ]'1 and f2, respectively. Recursively this
process is repeated yielding smaller and smaller frames until finally a frame
contains only one vertical edge. This is Case 1 of the algorithm which con-
structs L, R, P and S for this single edge. It is easy to check that after
completion L, R and P fulfill the output specification, though we didn't explain
yet the purpose of these sets. S is constructed in two steps: First, an " e m p t y "
set of stripes is formed, that is, all x u n i o n fields are assigned 0. The single
edge v leads to the construction of three stripes. Second, the stripe containing v
is selected and assigned the x-interval describing its coverage by the rectangle r
of which v is an edge. Hence now S = s t r i p e s ( { r } , ( x e x t , [ - - ~ , + oo]) and the
output specification holds. The resulting set of stripes can be represented (for
instance in case of a left edge):

+00

v.y-interva[t vN
-CO

x -ext
Fig. 5

In Case 2, the algorithm is given a set of vertical edges V located within some
frame f = ( x e x t , [ - 0% + ~ ] ) .
280 R.H. Gating

Fig. 6

In the divide step this area is divided into two subareas f l and f2, also
splitting V into 1/1 and V2.

VI V2

fl f2
Fig. 7

In the conquer step for each of these subsets and subareas a set of stripes is
constructed:

$1 $2
..............iiiiiiiwiiiiiiiiiiiiiiiN ii

fl f2
Fig. 8

In the merge step sets L, R, P and S are constructed from Li, R i, P~ and S ~, for
i = 1 , 2 . For L, R and P this is done in the obvious way; the subtraction of set
L R corresponds to removing rectangles that are completed in the merge step,
that is rectangles whose left edge is in V1 and whose right edge is in V2. In this
way L and R represent only edges of incomplete rectangles as required in the
output specification.
The construction of the set of stripes S is a little more difficult. It is done in
three steps copy, blacken and concat. We briefly illustrate these steps before
explaining them in detail.
First, the different y-partitions of S 1 and S 2 are made equal, that is, stripe
boundaries of S 1 are extended into S 2 and vice versa. In this step the coverage
of area in f l and f2, as given by x_union fields, is not changed. The copies of
S 1 and S 2 are called S~el~ and Sr~ght, respectively.
Computing Measure and Contour by Divide-and-Conquer 281

[
S tef t Sright

fl W f2
Fig. 9

Second, certain stripes in Sz~-, and S~ght are "blackened" (that is, their x_union
fields are updated) to indicate that they are completely covered by a rectangle.
Why it suffices to blacken complete stripes and how to select these stripes we
shall explain below.

S [eft 9:.:.:.:,:.:.:.:.:.:.:.:.:.:.:.:.:L:.:.~:.:.:, S right

iiiiiiiiiiiiiiiiiii!iiiifiiiiiiiiiIiiiiiiiiiiiiiiiii!!iiiI
fl iiiJ!i!iiiiii!iii!iti
ii!i!iiiiiiiii!!!i!ii!!i!ii
iii!iiiiiii
Fig. 10

Third, every two adjacent stripes in Steft and Sright (stripes with the same y-
interval) are concatenated to form the stripes of S. Again in this step the
coverage of area is not changed.

Fig. 11

This completes the construction of S=stripes (rect(V),f) as required in the

output specification.
Let us now examine the three steps copy, blacken and concat in more detail.
In the copy step copies Sze~t and Sright are produced from S a and $2, respective-
ly, that are based on the set P containing all partition points occurring in
either S 1 or S 2. This is done by the statements
Szer t : = copy ($1, P, [ x e x t . bottom, x,,]);
S,ig~t: = copy ($2, P, [x m, x e x t . top])
where
function c o p y (set of stripe S, set of coorfl P, interval x int)
set of stripe:
set of stripe S':-- {(ix, iy, 0)[ ix = x i n t and iy6partition(P)};
forall s' ~S' :
282 R.H, Gtiting

select s e S such that s . y _ interval ~_s'. y _ interval;

s'. x u n i o n : = s. x_union; (D)
S'
We know from the output specification that S~=stripes (rect(VO, f l ) and S 2
=stripes (rect(V2),f2). In other words $1 represents the union of the rectangles
represented in V~ by at least one edge (as far as it intersects fl), similarly S 2
those represented in V2. Since the copy step only introduces a finer y-partition,
Szelt and Sright still represent the same union, respectively. To construct S
representing the union of the rectangles represented by an edge in V= I/1u V2,
in the blacken step S~e/t is updated with respect to rectangles represented in V2,
similarly Sright for those in V1.
In the sequel we only describe the updating of S,ight (for S~eyt it is sym-
metric).
Lemma 3.1. Only those edges in V1 that are represented by an interval in L a \ L R
may cause changes of Srighr
Proof. Consider an arbitrary edge veV~ belonging to some rectangle r. There
are four cases:
a) v is a right edge

Sieft Sright

N! f2
Fig. 12

Then r does not intersect rE. Sright does not have to be updated.
b) v is a left edge with partner in V1.

S left Sright

fl f2
Fig. 13

Again r does not intersect f2 and Sright remains unchanged.

c) v is a left edge with partner in V2.

Sleft Sright

v NiiNi
I""~:..'.:~i'..:.i ~.:':.'.i|
fl f2
Fig. 14
Computing Measure and Contour by Divide-and-Conquer 283

Then the intersection of r with f2 is already represented in S,~gh~, because the

right edge is in V2 and participated in the construction of S,~gh~. S,~gh~ does not
have to be updated.
d) v is a left edge and the right edge of r is neither in V~ nor in V2.

iiiiliiiiiiiiiiiiiiliiiiiliii
v v [iiiiiiiiiliiiiiiiii!iiiiiiiiiiiiiiiiii
iiiiiiiiii#iiiiiiiii!iiiiiiiiiiiiiiiiiiiiiiiiiiii

Fig. 15

In this c a s e Sright has to be updated. Since the right edge of r is not in V2,
rectangle r covers the whole x-extension of area f2.
To summarize, only left edges in V1, whose partner is neither in V1 nor in
V2, may cause changes of S,ighr Precisely those edges are represented by their
y-intervals in LI \ L R . []
Lemma 3.2. Any stripe in Sright is either completely covered by a rectangle
represented in L~ \ L R or does not intersect such a rectangle.
Proof It suffices to observe that a stripe in S,igh, contains neither a horizontal
nor a vertical edge of such a rectangle. It contains no horizontal edge because
the y-partition of S,ight is based on the endpoints of all edges in Va u Vz. It
contains no vertical edge since for all rectangles represented in L a \ L R the left
edge is in VI (that is, left of f2) and the right edge to the right of f2.
Lemma 3.3, Precisely those stripes in S,~ght, whose y-interval is enclosed by some
y-interval in LI \ L R , are completely covered and have to be blackened.
Proof See the proof of Lemma 3.1, Case d). []
It follows that S~es~ and S,~ght are updated correctly by the two calls
blacken (Sleft, R 2 \ L R ) ;
blacken (S,ight, L 1\ L R )
where
procedure blacken (var set of stripe S, set of interval J):
forall s~S:
if exists i~J such that s. y_ interval ~_i
then s. x_union: = {s. x_interval} (E)
fi
Finally the stripes of S are obtained by concatenating the corresponding stripes
of Sl~ft and Sright:
S: = concat (Sl~it, Sright , P, x_ext)
where
284 R.H. Giiting

function concat (set of stripe $1, set of stripe $2, set of coord P,
interval x_int) set of stripe:
set of stripe S'.: {(i x, iy, 0)l ix = x _ i n t and iy~partition (P)};
forall s E S :
select s t e S 1 such that s I . y _ i n t e r v a l = s , y i n t e r v a l ;
select s2eS 2 such that s 2 . y _ i n t e r v a l = s , y _ i n t e r v a l ;
s. x_union: =s I .x_union & s 2 . xunion; (F)
S

The operation J & J ' denotes the c o n c a t e n a t i o n of two sets of intervals (basi-
cally the union, but two adjacent intervals at the b o u n d a r y are merged into
one). W e omit a formal definition.

4. Implementation

In Sects. 2 and 3 we have shown how to solve the measure and the contour
problem. D a t a and operations on them were described set-theoretically for
precision and clarity. H o w e v e r it is not obvious how to represent the data and
implement the abstract operations. This we will describe now.
We have already seen in Sect. 2 that the set of stripes is represented in
different ways for the measure and the c o n t o u r problem. We first describe
these representations. Later we look at the implementation of the whole algo-
rithm and determine its time- and space-requirements.

The Measure Problem

The question is for both the measure and the contour problem how to
represent s . x _ u n i o n . Recall that to solve the measure problem only m e a s u r e
(s. xunion) is needed. Hence we simply represent s . x u n i o n by a real n u m b e r
and define
type stripe = (interval x _ interval, interval y _ i n t e r v a l , real x _ m e a s u r e )
In Sect. 3, all lines describing operations on s . x _ u n i o n are marked by capital
letters. To solve the measure problem we simply replace these lines by the
following:
(A) S: = {(ix, iy, 0) ] ix = x e x t and i y ~ p a r t i t i o n (P)}
(B) s. x_measure: = x_ext, top - v. coord
(C) s.x measure,=[Link] -x ext. bottom
(D) s'. x m e a s u r e , = s . x _ m e a s u r e
(E) s. xmeasure: =s. x interval, top-s, x interval, bottom
(F) s. x measure: =s 1 . x measure + s 2 . x_measure

It is easy to check that these operations maintain the x-measure of a stripe

correctly.
Computing Measure and Contour by Divide-and-Conquer 285

The Contour Problem

As we have seen in Sect. 2 the representation of s . x _ u n i o n for the contour

problem must support a f r e e s u b i n t e r v a l q u e r y :
Given a set of disjoint x-intervals J and a query interval q = [xl, x2], report the
subintervals of q that are free with respect to J. (These subintervals are given
technically by i n t e r v a l s ( q \ ( q c ~ u n i o n ( J ) ) ) ) .
The representation we choose is a binary search tree storing the endpoints of
the intervals in s . x _ u n i o n in its leaves. A leaf also contains an indication
whether the represented point is a left or a right endpoint. This leads to the
definitions:
type stripe =(interval x_interval, interval y interval, ctree t r e e )
type c t r e e = empty ] (real x, iru side, ctree Ison, ctree r s o n )
type lru = atomic {left, r i g h t , u n d e f }
Again we describe operations (A)-(F):
(A) S: = {(ix, iy, empty) [ i x = x _ e x t and i y ~ p a r t i t i o n (P)}
(B) s . t r e e : = (v. c o o r d , left, empty, empty)
(C) s . t r e e : = (v. c o o r d , r i g h t , empty, empty)
(D) s'. t r e e : = s . t r e e
(E) s. t r e e : = empty
(F) s. t r e e : = i f s 1. t r e e : g e m p t y ~=s 2. t r e e then
(s 1 . x i n t e r v a l , t o p , u n d e r s 1 . tree, s 2 . tree)
[] s 1. t r e e 4= empty = sz. t r e e then s l . t r e e
[] s 1 . t r e e = empty + s 2. t r e e then s 2. t r e e
[] s 1 . t r e e = empty = s 2. t r e e then empty fi

F r o m the point of view of implementation it is important to note that the field

t r e e of a stripe contains a pointer to some structure. Especially the operations
(D) and (F) do not copy trees but manipulate pointers. Hence the three
operations c o p y , b l a c k e n and c o n c a t require only constant time per stripe. They
can be illustrated as follows:

copy

T ~ _~ s. t r e e

I I

s l 9t r e e
SI I:~:[:~:l [:[:~:??iJ
S2 NE:~:~:~I [iiiiiii!ii]
[:~:~:~:i:i:]
[Link]
s 3 .tree
S3
I Fig. 16
286 R.H. Gating

blacken

sl [ I
T ~ -- s tree

9 nil

i I
Fig. 17

concat

(Case: Both T 1 and T 2 a r e non-empty.)

Concat

s 1 .tree
$11 [i!i!i!i!il Ii!!i!i!!i@iiiiiiiil li!!i!i!i!iiiii!!it
$2 ~ T~ 1"2 ~ [Link]
•

imoooei
s I ~iiiiiiiil 1iiiiiiiiiiiiiii!iiiiiiiiiil[~i~i!iiiiiiiiil ' ~ ~.tre~

(Case : Both T1 and T2 are n o n - e m p t y . )

Fig. 18

The pointer operations have the effect that two trees belonging to different
stripes may have c o m m o n subtrees. On the conceptual level, however, this
doesn't matter and we can still maintain the view that each stripe has its own
separate tree. In fact, the collection of nodes accessible via the tree pointer of
any particular stripe s is simply a binary search tree.
Since [Link] is a search tree, it is certainly possible to answer a free
subinterval query with interval [Xl,X2] by visiting all nodes in the tree with x-
values between x~ and x 2. The additional information left/right in a leaf makes
it possible to report a free interval [a,b] within [ x l , x 2 ] for every pair of
subsequent leaves (a, right, empty, empty) and (b, left, empty, empty) found
between xl and x 2. This takes O(h+~) time where h is the height of the tree
and 7 the number of reported free intervals.
Computing Measure and Contour by Divide-and-Conquer 287

The Whole Algorithm and Its Complexity

The initial set V can be represented by an array; subsets then correspond to

array subranges. All the sets L, R, P and S are implemented by linked lists
ordered by y-coordinate. In case of the sets L and R, which contain intervals,
each interval is represented by its bottom and top point (so L and R are
represented by point lists). Scanning a list we keep a count of the number of
currently present intervals by adding 1 when encountering a bottom point and
subtracting 1 for an encountered top point. In this way it is easy to determine
whether the current position is covered by any interval in L or is free. This is
needed for the blacken operation. Matching points in both lists which repre-
sent L and R are omitted to perform the subtraction of the intersection set LR.

Time

Let us now look at the time complexity of the algorithm STRIPES. Let T(n)
denote the worst-case time STRIPES requires, applied to a set of cardinality n.
Obviously all operations in Case 1 take only constant time, hence

T(1)=O(1) (1)

In Case 2 dividing can be done in constant time and the conquer step yields
two terms T(n/2). All operations in the merge step can be performed by
scanning lists in parallel. We leave it to the reader to check that the operations
during those scans take only constant time for each list element. Hence the
operations in the merge step require linear time in total. Therefore

T(n) = O(1) + 2 T(n/2) + O(n) (2)

It is well known that the recurrence Eqs. (1) and (2) have solution

T(n) = O(n log n)

(see for instance [1]).

Space

Clearly the array representing V and the linked lists representing L, R and P
require O(n) space. The space requirements of the data structure representing
the set of stripes S is different for the measure and the contour problem.
In case of the measure problem the representation of each stripe takes only
constant space, hence the whole set S can be stored in O(n) space.
In case of the contour problem we have to look at the way a set of stripes
is created. Let SP(n) denote the worst-case space-requirements of a set of
stripes constructed by algorithm STRIPES when applied to a set V of cardi-
nality n. Case 1 of the algorithm constructs a set S using constant space, hence

SP(1) = 0(1)
288 R.H. Gi,iting

In Case 2 of the algorithm the set of stripes is constructed in the merge step.
Observe that a new linked list is created with O(n) elements (each element
representing a stripe) and that for each list element at most a new root node
and two pointers are created. The tree structures belonging to stripes of $1 and
S 2 are retained. Hence
SP(n) = 2 SP(n/2) + O(n)

These are the same recurrence equations as above with solution

SP(n) = O(n log n)

We have to add a few words on the complexity of obtaining the actual

solution for each problem from the data structure representing S. H o w to
obtain this solution is described in Sect. 2. For the measure problem the linked
list representing S is scanned, summing the 2-dimensional measure of each
stripe. Clearly O(n) time is sufficient. For the contour problem the horizontal
rectangle edges are sorted by y-coordinate into a list HRE. This list is then
scanned in parallel with the linked list of stripes. For each horizontal edge a
free subinterval query is performed on the corresponding stripe's tree. Since the
height of this tree is O(log n), each query takes O(log n + ~) time (~ the number
of reported contour pieces) yielding a total time of O(nlogn+p) where p is the
total size of the contour (the number of contour pieces). Using the method of
[-12] the contour can then be constructed as a set of linked contour cycles in
O(p) time and space.
We summarize our results in:
Theorem 4.1. For a set of n rectangles the measure problem and the contour
problem can be solved by divide-and-conquer. This takes O(nlog n) time and O(n)
space in case of the measure problem and O ( n l o g n + p ) time and space for the
contour problem, where p is the size of the contour.

Multiple x- or y-Coordinates

We now drop the initial restriction that the x- and y-coordinates of all
rectangles have to be pairwise distinct. F r o m now on we only assume the x-
and y-coordinates of any particular rectangle to be distinct, that is, the rectan-
gle does not degenerate to a line segment or a point.
To accomodate multiple x- or y-coordinates we slightly modify the algo-
rithm or its implementation, respectively. Concerning multiple x-coordinates it
is not obvious anymore how to split the set of edges V in the divide step since
many edges may share an x-coordinate. We proceed as follows: In the initial
sorting of all vertical rectangle edges (Step 1 of algorithm
R E C T A N G L E _ D A C ) all left edges are put before all right edges with the same
x-coordinate in the sorted order. Input for algorithm S T R I P E S is then a sorted
sequence of edges V=v i ... vj (initially v 1 ... V2n ) which is divided by selecting a
median edge vm and forming Vl=vi...v,, and Vz=vm+ 1 ...vj. The condition
"left edges appear before right edges" ensures a correct functioning of the
algorithm in situations like that depicted in Fig. 19a):
Computing Measure and Contour by Divide-and-Conquer 289

s, N NiiNii!!l s, iiiiii!/i!!iNN!i

• •
o b
Fig. 19

In this case a left and right edge on the same x-coordinate x 0 remove each
other in the blacken operation such that no interval boundary remains in stripe
s i. It is also easy to check that from a group of left edges sharing an x-
coordinate (see Fig. 19b)) only one edge survives the blacken operations to
form an interval boundary in stripe si.
The trees representing s.x_union constructed by the algorithm may now
contain internal nodes and leaves with the same x-coordinate. However, since
all leaves have distinct x-coordinates, at most two internal nodes and one leaf
may have the same x-coordinate. It is not difficult to adapt the free subinterval
search algorithm to this case.
Concerning multiple y-coordinates it becomes a problem to compute ef-
ficiently the intersection set L R = L ~ R 2. Obviously it doesn't suffice anymore
to look for list elements with the same y-coordinate in the lists (representing)
L~ and R 2. Therefore we initially assign a unique identification number to
each rectangle (for instance the numbers 1..... n). Each element of an interval
list is augmented by the number of the rectangle from which it originates. The
resulting pairs (y-coordinate, rectangle number) are kept in lexicographical
order in the lists. That is, the merge step maintains this order which is given
trivially in the initial lists built in Case 1 of algorithm S T R I P E S . - Since there
exists again a total order on the list elements it is once more possible to form
the intersection of Lt and R 2 (in other words to detect common elements in
both lists) in linear time.
Clearly the modified algorithm has the same time- and space-complexity
and treats multiple x- and y-coordinates correctly.

5. Conclusions

In this paper we presented time-optimal divide-and-conquer solutions for the

measure and the contour problem. The central part of the solution is algorithm
S T R I P E S computing a compact representation stripes of the union of a set of
rectangles.
Data structure stripes (in its specialization for the contour algorithm) essen-
tially provides a partition of union (R) into disjoint rectangles. As such it might
have other applications, for instance, based on stripes it is possible to compute
efficiently integrals ranging over union (R). If several integrals are to be com-
puted then it seems reasonable to maintain data structure stripes independently
290 R.H. Giiting

from algorithm S T R I P E S . This could be appropriate in various situations

where different properties of one set of rectangles are of interest.
The results of this paper were achieved using a new approach to divide-
and-conquer called "separational representation" of planar objects. Together
with a previous paper [11] the following problems have so far been solved
using this technique:
1) Finding all intersections in a set of horizontal and vertical line segments.
2) Finding all point enclosures in a mixed set of points and rectangles.
3) The rectangle intersection problem, by combining 1) and 2).
4) The measure problem.
5) The contour problem.
This seems to be sufficient evidence to support the belief that for problems
involving iso-oriented planar objects divide-and-conquer using separational
representation is as powerful as the line-sweep paradigm. As a consequence,
when dealing with new problems of this kind, it seems advisable to try both
algorithmic paradigms. Perhaps there exist problems which can be solved more
easily by divide-and-conquer than by line-sweep.
Comparing both paradigms, a certain trade-off seems to take place: With
divide-and-conquer, more complexity is put into the structure of the algorithm.
As a result the data structures become more simple and easier to maintain.
With line-sweep, the structure of the algorithm is more simple, which has to be
paid for by an increased complexity of the supporting data structures.
We suggest the following directions for further work:
1) Define a class of problems for which both paradigms are equivalent. That is,
whenever a line-sweep algorithm exists to solve a problem in this class, then
the corresponding divide-and-conquer algorithm can be given and vice-versa.
2) Study the relation between corresponding data structures. For instance for
the measure problem the corresponding data structures are a linked list of
numbers and the segment tree. Is it possible to give rules how to define the
"partner" data structure, if one of them is given?
3) Line-sweep algorithms have been used successfully to solve problems involv-
ing non-orthogonal objects (for instance see the algorithm finding all in-
tersections in a set of arbitrarily oriented line segments in 2-space [3]). Can the
applicability of divide-and-conquer be extended to this kind of problems?
4) Try divide-and-conquer on problems for which time-optimal line-sweep
algorithms could not yet be obtained.

Acknowledgements. 1 would like to thank Derick Wood for his encouragement during this work
and Armin B. Cremers for his comments on the manuscript. Thanks also to two a n o n y m o u s
referees for m a n y useful remarks that led in particular to a cleaner notation for algorithms and
data structures.

References

1. Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The design and analysis of computer algorithms.
Reading, M A : Addison-Wesley 1974
Computing Measure and Contour by Divide-and-Conquer 291

2. Bentley, J.L.: Solutions to Klee's rectangle problems. Carnegie-Mellon University, Department

of Computer Science, 1977 (Unpublished)
3. Bentley, J.L., Ottmann, T. : Algorithms for reporting and counting geometric intersections.
IEEE Trans. Comput. C-28, 643-647 (1979)
4. Bentley, J.L, Shamos, M.I.: Optimal algorithms for structuring geographic data. In: Proceed-
ings, Symposium on Topological Data Structures for Geographic Information Systems, Har-
vard University, pp. 43-51, 1977
5. Bentley, J.L., Wood, D.: An optimal worst-case algorithm for reporting intersections of re-
ctangles. IEEE Trans. Comput. C-29, 571-577 (1980)
6. Eastman, C.M., Lividini, J.: Spatial search. Carnegie-Mellon University, Institute of Physical
Planning, Report 55, 1975
7. Edelsbrunner, H.: Dynamic rectangle intersection searching. Technical University of Graz,
Institut fiir Informationsverarbeitung, Report F47, 1980
8. Edelsbrunner, H., van Leeuwen, J., Ottmann, T., Wood, D.: Connected components of orthogo-
nal geometrical objects. RAIRO Theoretical Informatics 18, 171-183 (1984)
9. [Link], R.H. : An optimal contour algorithm for iso-oriented rectangles. McMaster University,
Unit for Computer Science, Report 82-CS-03, 1982 (To appear)
10. Gtiting, R.H. : Conquering contours. Efficient algorithms for computational geometry. Universi-
tat Dortmund, Lehrstuhl Informatik VI, Ph.D. Thesis, 1983
11. Giiting, R.H., Wood, D.: Finding rectangle intersections by divide-and-conquer. IEEE Trans.
Comput. C-33, 671-675 (1984)
12. Lipski, W., Preparata, F.P.: Finding the contour of a union of isooriented rectangles. J.
Algorithms 1, 235-246 (1980)
13. McCreight, E.M.: Efficient algorithms for enumerating intersecting intervals and rectangles.
XEROX Palo Alto Research Center, Report CSL-80-9, 1980
14. Mead, C., Conway, L.: Introduction to VLSI-Systems. Reading, MA: Addison-Wesley, 1980
15. Shamos, M.I., Hoey, D.: Geometric intersection problems. Proceedings of the 17th Annual
IEEE Symposium on Foundations of Computer Science, pp. 208-215, 1976
16. Soisalon-Soininen, E., Wood, D.: Optimal algorithms to compute the closure of a set of iso-
rectangles. J. Algorithms 5, 199-214 (1984)

Received September 3, 1982/June 18, 1984

Note Added in Proof

Recently another time-optimal line-sweep algorithm for the contour problem was found by Wood:
Wood, D., The contour problem for rectilinear polygons. University of Waterloo, Computer
Science Department, Report CS-83-20, 1983
It can be seen as an improvement of [-9] because the data structure supporting the line-sweep is
simpler