Robotics Research

Ifechnical Report

f^MMi^ll^

|*a,

The Complexity of Many Faces

in Arrangements of Lines and

of Segments

by

Herbert Edelsbrunner

Leonidas J. Guibas

Micba Sbarir

Technical Report No. 358

Robotics Report No. 146

March, 1988

\

New York University

Courant Institute of Mathematical Sciences

Computer Science Division

25 1 Mercer Street New York, N.Y 1 00 1 2

The Complexity of Many Faces

in Arrangements of Lines and

of Segments

by

Herbert Edelsbrunner

Leonidas J. Guibas

Micha Sharir

');
}
elseif (getClientWidth() > 430)
{
document.write('');
}
else
{
document.write('');
}
//-->

Technical Report No. 358

Robotics Report No. 146

March, 1988

New York University

Dept. of Computer Science

Courant Institute of Mathematical Sciences

251 Mercer Street

New York, New York 10012

The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev.

Comput. Sci. 1-6-44862 and the National Science Foundation under grant CCR-7614575.

Work on this paper by the third author has been supported by Office of Naval Research

Grant N00014-87-K-0129, by National Science Foundation Grant. No. NSF-DCR-83-20085,

by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a

research grant from the NCRD — the Israeli National CouncU for Research and Develop-

ment.

THE COMPLEXITY OF MANY FACES IN ARRANGEMENTS

OF LINES AND OF SEGMENTS^

Herbert Edelsbrunner , Leonidas J. Guibas and Micha Sharir"*

Abstract. We show that the total number of edges of m faces of an

arrangement of n lines in the plane is 0(m ' ~ n ' ^ +n), for any (5>0.

The proof takes an algorithmic approach, that is, we describe an algorithm

for the calculation of these m faces and derive the upper bound from the

analysis of the algorithm. The algorithm uses randomization and, with high

probability, its time complexity is 0(m'^'^~ ra^' logn+nlognlogm). If

instead of lines we have an arrangement of n line segments, then the max-

imum number of edges of m faces is 0{m'^'^~ n +na(n)logm), for any

(5>0, where o.[n) is the functional inverse of Ackermann's function. We give

a (randomized) algorithm that produces these faces and, with high probabil-

ity, takes time 0(m^' ~ n"'"'*^ logn -(- nQ(n)log^nlogm).

Keywords: Combinatorial geometry, computational geometry, arrange-

ments of lines and line segments, random sampling, probabilistic counting,

divide-and-conquer, partition trees, randomized algorithms.

The first author Is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput.

Sci. 1-6-44882 and the National Science Foundation under grant CCR-8714565. Work on this paper

by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by Na-

tional Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Cor-

poration, and the IBM Corporation, and by a research grant from the NCRD - the braeli National

Council for Research and Development.

^Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois

81801, USA.

DEC Systems Research Center, Palo .\lto, California 94301, and Department of Computer Sci-

ence, Stanford University, California 94305, USA.

*Courant Institute of Mathenaatical Sciences, New York University, New York, New York 10012,

USA. and School of Mathematical Sciences, Tel Aviv University, Tel .\viv, Israel.

1. Introduction

Let L ={/j,/2,...,/n } b^ ^ finite set of lines in the plane. L induces a partition of the

plane, known as the arrangement A{L) of L, into O(n^) faces, edges, and vertices.

The vertices are the points of intersection of the lines in L, the edges are the con-

nected components of the lines after removing the vertices, and the faces are the (con-

vex) connected components of the complement of the union of the lines /, (see [Gr; or

[Ed] for more details concerning arrangements in the plane and in higher dimensions).

Many combinatorial properties of arrangements of lines have been studied exten-

sively. In this paper we consider the maximum number, K[m,n), of edges bounding

m distinct faces in an arrangement of n lines in the plane (where we count an edge

twice if it bounds two of these faces). Note that m can vary between 1 and

K(n) = (-)+n-f 1, and that at these extreme values we have K{l,n) = n and

A'(/c(n),n) =2n' (there are altogether n" edges in the arrangement and each edge

bounds two faces). A trivial upper bound for K{m,n) is mn and a trivial lower

bound is m. Prior to this and a companion paper [CEGSWl, the best known bounds

on K{m,n) for general values of m were

[Cal,

(i) K{m.n) = n+4Cp for m >2 and n >4(2)

(ii) A'(m,n) = 0(mn'/2) for cn^/2

i

1

n

i

A 6 .8 1.0 1.2 1.4 1.6 1 8 20

Figure 1.1. Previous bounds on K(m,n).

In this paper we improve the upper bounds by showing that

for any positive 6 (with the constant of proportionality depending on Sy. In particu-

lar, when m = n we obtain

K{n,n) = 0{n^/^^^)

for any 6>0. Our bound almost matches the lower bound K{m,n) = ri{m'^' n ' )

obtained by Edelsbrunner and Welz! [EWj. We mention that our upper bound is

almost the same as the upper bound due to Szemeredi and Trotter [ST! on the max-

imum number of incidences between m points and n lines.

Our approach to the combinatorial problem is different from previous work on

this problem in that it has an algorithmic flavor. We obtain an algorithm for the cal-

culation of m faces in an arrangement of n lines, where each face is designated by

specifying an arbitrary interior point in it. In other words, we consider n lines,

/j,/2, ...,/„, and m points, p,,P2,...,p^, in the plane, and calculate the faces of the

arrangement that contain the given points (see Figure 1.2; for reasons that will

become clear later we allow more than one point designating a single face). We con-

struct these faces using the following divide-and-conquer strategy which mimics the

construction of and search in a so-called partition tree which is a data structure

designed for half-plane or triangle range queries (see EW2 and HW ). It will be

convenient to describe this tree in dual space although it is possible to find a fairly

natural interpretation of it also in primal space. For this reason, we dualize the

points and lines and thus obtain lines p, * and points /, * in the dual plane. Those

lines will be referred to as dual lines and the points will be called dual points. The

tree that we construct can be interpreted in two different ways. Thinking of the dual

Figure 1.2. Points designate desired faces.

With some effort, one can determine for each m and n the optimal choice of c, and thus obtain a

somewhat tighter bound for A'(m,n).

points as data and the dual lines as queries, we obtain a partition of the set of points

into disjoint subsets, according to some underlying convex decomposition of the plane;

this is similar to standard partition trees [EW2I, [H\Vi, except that we use the a priori

given query dual lines to form the partition, thus making the tree "customized" and

easier to search. An alternative point of view is to think of the dual lines as the data

and the dual points as the query objects. In this interpretation, the partition tree that

we build differs from standard partition trees in two important aspects — it uses

superlinear space since it duplicates data, and is again "customized" for the query

objects (the dual points). In particular, we use a stopping rule based on the relation

between the num.bers of points and lines at any node which decides whether or not

the tree is continued below this node. Whichever point of view we take, it is impor-

tant to keep in mind that both data and queries are available in advance, and that

the tree is a function of both. Since the tree may have superlinear size, we will not

attempt to really construct it but rather traverse it and build and destroy its nodes as

we go. Indeed, the partition tree can be seen as a materialization of the algorithm

and exists only on a conceptual level.

Of course, what we want to achieve is the calculation of the faces containing each

of the given points, rather than processing half-plane range queries. However, the

two problems turn out to have a lot in common, so that they are both amenable to

the partition tree technique. Nevertheless, the two problems require different actions

when it comes to combining information from the children of a node to produce the

output at that node. This is a fairly trivial step in range searching but requires some

sophisticated machinery in our case. Specifically, for a node v of our tree and for

each (primal) point p that reaches that node, we want to construct the face in the

arrangement of the (primal) lines that reach v. This is accomplished by combining

the faces containing p in each of the subarrangements corresponding to the children

of V. A major tool that we develop for this purpose is the so-called "combination

lemma" which gives a tight upper bound on the maximum combinatorial complexity^

of the desired faces in terms of the combinatorial complexity of the corresponding

faces in the subarrangements (see Lemma 1). We expect this result to have applica-

tions to other problems as w^ll.

To re-iterate, we present a technique for constructing a partition tree for a set of

"data" points and a predetermined set of "query" lines. Such a tree can then be used

(a) to obtain better bounds for batched half-plane range searching

when the queries are known in advance (applications include calculating the

"signature" of a polygonal curve OR], multiple ray-tracing ^SMLj, etc.),

(b) to obtain our bounds on the complexity of many faces in arrange-

ments of lines (or of line segments, as studied in Sections 4 through 7), and

(c) in many other applications of a similar nature, such as reporting or

We use the term "combinatorial complexity" and sometimes just "complexity" for the number of

edges bounding some collection of faces.

counting the intersections between n given line segments (see [GOS;).

In our present application, the desired upper bound on K{m,n) is obtained by analyz-

ing the space complexity of the resulting algorithm. The time complexity of the algo-

rithm is roughly a poly logarithmic factor times the upper bound on K{m,n) men-

tioned above (see Section 3 for a more precise bound). The algorithm is based on a

random sampling technique akin to the f-net method of Haussler and Welzl [HW^ and

to the random sampling method of Clarkson [CI]. We obtain a randomized algorithm

which always terminates and produces the desired output and which, with high pro-

bability, does so within the stated time bound.

Next we consider the problem of estimating the maximum number of edges

bounding m faces in an arrangement A of n line segments in the plane, and of calcu-

lating these faces. This problem is considerably more difficult than for lines, because

the faces of A are not necessarily convex or simply connected. This makes it harder

to process such faces efficiently. Nevertheless, using an intricate extension of our

combination lemma (see Lemma 5), we obtain essentially the same bound on the max-

imum complexity, R{m,n), of m distinct faces in an arrangement of n line segments.

More precisely, we prove

R(m,n) = 0(m2/^-*n2/^*" + na(n)logm)

for any (5>0, where a(n) is the extremely slowly growing inverse of Ackermann's

function. To the best of our knowledge this is the first non-trivial upper bound

known for R{m,n). Note that this upper bound almost matches the above mentioned

lower bound on K(m,n). Since trivially K{m,n)0, n >0. However,

when both functions are defined, we clearly have K{m,n)=K{m,n).

We next describe the algorithm for calculating the required faces. The discussion

will ignore implementation issues (addressed in Section 3) and instead concentrate on

combinatorial problems that arise.

First we dualize the lines /, to points /, * and the points p, to lines p, *. This

gives a set L* of n points and a set P* of m lines in the dual plane. To process the

dual points and lines, we choose some constant integer r >0, and select a random

sample of r of the dual lines p^*. When we draw the arrangement of these lines in

the dual plane and triangulate each of the faces of this arrangement we obtain a total

of iV/=0(r") triangles. The 6-net theory of Haussler and Welzl [HWj or, alterna-

tively, the random sampling lemma of Clarkson [CI] imply that, with high probabil-

CTTl

ity, the interior of each of these triangles intersects at most logr dual lines, for

r

some constant c. We now build a partition tree, T, as follows. Each node of T is

associated with some subset of the dual points of L* and with some subset of the dual

lines of P*. Let t; be a node of T that is associated with L^*C.L* and P^*C.P*. The

points in L„* and the lines in P„* (as well as their primal counterparts) are said to

reach v. We take a random sample of r lines from P„ * and construct and triangulate

their arrangement. For each triangle J^, in this arrangement we form a child w of v

in T and associate with w the subset L^' of the dual points of L„* contained in A^

and the subset P^* of dual lines of P„* that intersect the interior of A^. (A

schematic representation of this process is shown in Figure 2.1; the arrangement is

formed by r=2 lines, thus it is not necessary to further decompose the four faces

which correspond to the four children of v.) In what follows we will denote the cardi-

nality of Z,„* by rip and the cardinality of P„* by m„^.

This process is continued recursively, but not all the way until just one or no

point or line remains. Whenever we reach a node t; of T for which m„ >«:(«„), we

slop the process and undo the dualization to obtain L^ from L^* and P„ from P„*.

Then we construct the arrangement A{L^) (in the primal plane), locate® in it each of

The reader is advised to note that we consistently use the letters L and n in association with the

primal lines (and therefore with the dual points) and that P and m are used in connection with primal

points (and thus dual lines).

_ .^- . . / . . '^N

" — ~*/ • ^ • ^^ \

Figure 2.1. Partition tree and corresponding decomposition.

the points of P^,. and report the faces of A(Z.J that contain them, .\nother case

where we stop in the construction of 7 at node v is if F„* =0. In this case we do not

have to bother constructing A[L^'] since there are no points for which faces need to be

calculated.

During this process we construct the required collection of faces of A[L) as fol-

lows. For each node v of T and for each point p, reaching v during the above con-

struction, let Fp(p, ) denote the face of the arrangement A{L^) that contains p, .

(Recall that such a face will be shared by all points reaching u that lie in it.) These

faces are constructed bottom-up as follows.

(i) .\s mentioned above, at each leaf u of T we either have m„ >K;{n^, )

or mt,=0. In the first case we construct the entire arrangement of the n^,

corresponding lines r, locate in this arrangement each of the m„ points p, of

P„*, and collect the corresponding faces ft,(p,) (each face only once). The

total number of edges bounding these faces (which is proportional to the

space needed to store them) is at most 0{n^')=0[m^\ In passing we men-

tion that the time-complexity of this step is at most

0( n„^+m„ log nj,) = 0(mj, log rz„) using the arrangement construction algorithm

of EOS] and the optimal point location structure of [EGSt].

(ii) At each node v of T, compute Q„ =P^—P„, u the parent of v, and

let 6„ be the cardinality of Q^. Q^ is the set of points whose dual lines inter-

sect the interior of A^ but miss the interior of J^. By duality, each of these

points p, lies either above all the lines in L^ (in the topmost face F~ of

A{L^)) or below all of them (in the bottommost face F~). This is illustrated

in Figure 2.2. These two faces together have at most n^+2 edges, and they

can be constructed in time 0{njo%n^) (see e.g. PS). As required, we store

each of these two faces just once, and maintain a pointer from each point

^Locating a point in an arrangement means to find the face (or edge or vertex) of the arrangement

that contains the point. It is a fairly common term in computational geometry which, among other

things, considers data structures that facilitate fast point location queries (see e.g. EGSt ).

DUAL

PRIMAL

t,'

Pz'

Figure 2.2. Dual and primal plane.

p,GQ„ to either F^ or F^7 whichever contains it. We note that the topmost

and bottonimost faces in A{L^) must be constructed even if m„ =0 and we

stop the construction of the tree below v.

(iii) The general recursive step at any internal node i; of T proceeds as

follows. Let u-'i.u; 2,. ••'"-'.;/■ ^^ the children of v (recall that M = 0(r^)). For

each point p, that reaches v (that is, its dual line intersects Z\„ and the tri-

angles of all ancestors of v) and for each child w of t;, either p, belongs to

Q^ or p, reaches w^, in which case the face F^{p,) containing p, has been

calculated recursively. Our task is now to take the M faces containing p,

(where each such face is either of the form F^{p,) or is one of F~ , F~_ asso-

ciated with Q^) and to form their intersection to obtain Fp(p, ). This inter-

section is clearly a convex polygon that contains p, and the number of its

edges is at most the sum of the number of edges of the intersected faces.

However, since some of the faces may be shared by other points, we

need to avoid duplicate processing and counting of the same face for each

point it contains, or else our algorithm might have unacceptably high time-

complexity and our upper bound on the total number of edges will be annoy-

ingly loose. A typical case where duplicate processing of this sort can slow-

down the algorithm is depicted in Figure 2.3.

A solution to this problem is provided by the following technical lemma, which we

refer to as the "combination lemma (for lines)".

Figure 2.3. Six faces designated by three points each.

Lemma 1. Let p^.p2,. - ,Pk be points in the plane, and let {8^,82 B,} and

{Ri,R2, - Mt\ be collections of 5 "blue" and t "red" open convex polygons

that satisfy the following three conditions.

(i) The blue (red) polygons are pairwise disjoint and the total

number of blue (red) edges is P [p].

(ii) Each point p, is contained in a blue polygon B, and in a

red polygon R^ .

(iii) If for each 1