Herbert Edelsbrunner.

The complexity of many faces in arrangements of lines and of segments online

. (page 1 of 4)
Font size
QR-code for this ebook

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



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


1 3 4