C It

Discrete Comput Geom **:***-*** (****)

Geometry

Discrete & Computational

* **** ********-****** *** York Inc.

N ew Bounds for Lower Envelopes in Three Dimensions,

with Applications to Visibility in Terrains*

D . H a l p e r i n l t a n d M. S h a r i r L2

School of Mathematical Sciences, Tel Aviv University,

Ramat Aviv, 69978 Tel Aviv, Israel

abpjms@r.postjobfree.com

sharir @math.tau.ac.il

2 C ourant Institute of Mathematical Sciences, New York University,

251 Mercer Street, New York, NY 10012, USA

Abstract. W e consider the problem of bounding the complexity of the lower

e nvelope of n surface patches in 3-space, all algebraic of constant maximum degree,

a nd bounded by algebraic arcs of constant maximum degree, with the additional

p roperty that the interiors of any triple of these surfaces intersect in at most two

p oints. We show that the number of vertices on the lower envelope of n such surface

p atches is O(n z" 2c],/ig~), for some constant c depending on the shape and degree of

t he surface patches. We apply this result to obtain an upper bound on the combinator-

i al complexity of the "lower envelope" of the space of all r ays i n 3-space that lie

a bove a given polyhedral terrain K with n edges. This envelope consists of all rays

t hat touch the terrain (but otherwise lie above it). We show that the combinatorial

l ogn

c omplexity of this ray-envelope is O(n 3 92c ],/i~) for some constant c; in particular,

t here are at most that many rays that pass above the terrain and touch it in four

e dges. This bound, combined with the analysis of de Berg e t al. [4-1, gives an upper

b ound (which is almost tight in the worst case) on the number of topologically

d ifferent orthographic views of such a terrain.

* W ork on this paper by the first author has been supported by a Rothschild Postdoctoral

Fellowship. Work on this paper by the second author has been supported by NSF Grant CCR-

91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the

G erman-lsraeli Foundation for Scientific Research and Development, and the Fund for Basic Research

administered by the Israeli Academy of Sciences.

t C urrent address: Robotics Laboratory, Computer Science Department, Stanford University,

Stanford, CA 94305, USA.

314 D. Halperin and M. Sharir

1. Introduction

L et E = {al . . . . . a,} be a given collection of n surface patches in 3-space. This

p aper addresses the problem of bounding the combinatorial complexity of the

l ower envelope (pointwise minimum) of the surface patches in E. Assume for

s implicity that each a~ is the graph of a partially defined function z =f~(x, y),

a nd that these functions, as well as the curves delimiting the patches, are all

a lgebraic of constant maximum degree, and that the given surfaces are in general

p osition (see Section 2 for precise definitions). The lower envelope, when

p rojected onto the xy-plane, generates a planar map ~', called the minimization

diagram o f E [15], with the property that over each face of ~r the envelope

is attained by a single patch (or by no patch at all), over each edge the envelope

is attained by two patches simultaneously or by the boundary of a single

p atch, and over each vertex of Jr' the envelope is attained by three patches

s imultaneously, or by the intersection of the boundary of one patch with another

p atch, or by a point on the boundary of one patch which lies directly below

t he boundary of another patch, or below an intersection curve of two other

p atches (so that this higher point is vertically visible from the point on the lower

b oundary), or by a vertex of a patch boundary (a point where two arcs forming

t his boundary meet). The combinatorial complexity of the envelope is defined

s imply as the overall number of faces, edges, and vertices of ~ ', and is denoted

b y ~k(E).

U nder the assumptions made above, it is easy to show that if(E) = O(n3) ( with

a c onstant of proportionality that depends on the algebraic degree of the patches

a nd of their boundaries). However, it has been conjectured over the past 8 years

t hat the maximum possible complexity of such an envelope is only about quadratic

i n n.

T he conjecture is motivated by the fact that in two dimensions, in the case of

t he.lower envelope of n partially defined univariate functions, sharp bounds are

k nown for the complexity of the envelope, measured simply in terms of the number

o f breakpoints a long the envelope. If each pair of the functions intersect in at most

s p oints, then the complexity of their envelope is at most 2~+2(n), which is the

m aximum length of Davenport-Schinzel s equences of order s + 2 composed of n

s ymbols (see [2] and [11] for more details), and is only slightly superlinear in n

f or any fixed s. The conjecture in three dimensions attempts to extend this bound,

a nd asserts that the complexity of the envelope is O(n2q(n)), f or some constant q

d epending on the degree and shape of the given patches. The conjecture appears

t o be extremely difficult, and has been proven i'or ~amilies of only a few types of

s urface patches, such as triangles, and a few other types (see [13] and [15]). Better

b ounds are known for the special cases of planes and balls. The problem in general

h as been wide open; in fact, no general bounds better than O(n 3) were known

s o far.

I n this paper we obtain a subcubic bound for the complexity ~k(E), provided

t he given surface patches are such that the interiors of any three of them intersect

i n at most two p oints. In fact, our bound is close to quadratic, so we almost

N ew Bounds for Lower Envelopes in Three Dimensions 315

e stablish the conjecture in this special case. This property holds in several

a pplications. As a matter of fact, if the given surfaces had this property and were

full surfaces without boundary, then the results of [15] would imply (with a few

a dditional mild assumptions) that the complexity of their envelope is O (n2).

H owever, the fact that they are surface patches makes the analysis more difficult,

a nd this bound is not known in that case.

O ur main result is that, under the above assumptions, the complexity of the

l ower envelope of these surfaces is O (n 2 9 2 c ~ ), for some constant c that depends

o n the degree and shape of the given surfaces. The proof is not difficult, and relies

o n the randomized technique of [7] and [16-] for obtaining generalized " (

b ounds in arrangements. This result still leaves a small gap from the conjectured

c omplexity, but is nevertheless a significant and rather decisive step toward the

e stablishment of the conjecture.

I n a companion paper [17] the technique presented in this paper is extended

t o obtain similar, almost-tight bounds in more general setups, both when the

m aximum number of points of intersection between a triple of surfaces can be

l arger than two (but still remains a constant), and when the dimension is larger

t han three.

O ur result was motivated by, and has an interesting application to, the problem

m entioned in the abstract, namely, the problem of bounding the combinatorial

c omplexity of the "lower envelope" of the space of all rays in 3-space that lie

a bove a given polyhedral terrain K with n edges. This envelope consists of all rays

t hat touch the terrain (but otherwise lie above it). We show that the combinatorial

c omplexity of the envelope is O ( r t 3 9 2cl x/~) for some constant c; in particular, there

a re at most that many rays that pass above the terrain and touch it in four edges.

T his bound is derived by applying the three-dimensional envelope result n times,

e ach time fixing an edge e of K and considering the three-dimensional space of

all lines (or rays) that touch e but otherwise pass above K. It is fairly easy to show

( and indeed is shown in Section 3) that the conditions required by our analysis hold

in this application. Our bound for the complexity of the space of lines passing

a bove a terrain was recently, and independently, obtained by Pellegrini [14], but

it is not clear whether his result can be extended to the space of rays passing above

a t errain.

T his bound on the complexity of the envelope of the space of rays over a terrain

h as an interesting application to the problem of bounding the number of topologi-

c ally different orthographic views of such a terrain. A recent study by de Berg e t

al. I -4] gives a bound of O (n s" 2 ~"1) for this number, but unfortunately their

a rgument turned out to be erroneous. A careful (and correct) restatement of the

r esult of de Berg e t al. is that the bound on the number of topologically different

o rthographic views of a terrain is O (n24(n)p(n)), w here p(n) is the maximum

c omplexity of the ray-envelope of a terrain with n edges. Plugging in our bound

for/~(n), we get the bound O (n 5 " 2c~ )ogn for the number of views, for some absolute

l

c onstant c. Except for a remaining small factor, this result almost matches the

u pper bound originally asserted in [4], and, as shown in [4], is almost tight in

t he worst case.

316 D. Halperin and M. Sharir

2. Lower Envelopes in 3-Space

L et Y~= {tr 1. . . . . a,} be a given collection of n surface patches in 3-space that

s atisfy the following conditions:

(i) Each o~ is monotone in the xy-direction (that is, every vertical line intersects

~ i n at most one point). Moreover, each cr~ is a portion of an algebraic

s urface of constant maximum degree b.

(ii) The vertical projection of tri onto the xy-plane is a planar region bounded

b y a constant number of algebraic arcs of constant maximum degree (say,

b t oo).

(iii) The relative interiors of any triple of the given surfaces intersect in at most

t wo points.

(iv) The surface patches in E are in general position. T his excludes degenerate

c onfigurations where four surfaces meet at a point, the boundaries of two

s urfaces meet, the boundary of one surface meets an intersection curve of

t wo other surfaces, a pair of surfaces are tangent to each other, a singular

p oint on one surface lies on the boundary of another surface or on an

i ntersection curve between two other surfaces, etc.

C onditions (i)-(iii) are essential for the analysis, while condition (iv) is made

t o simplify the forthcoming arguments. It involves no real loss of generality,

b ecause, as can be shown (see the companion paper [17] for details), the

m aximum complexity of the envelope is achieved, up to a constant factor,

w hen the given surfaces are in general position. We also note that the first

p art of condition (i) is not essential, because we can always cut a surface

tr along the constant number of arcs which are the loci of points on a having

v ertical tangency, to obtain a constant number of xy-monotone surfaces whose

u nion is o.

T he lower envelope o f E is the graph of the (partial) function z = E~(x, y)

t hat maps each point (x, y) to the height of the lowest point of intersection

b etween the vertical line through (x, y) and the surfaces in Y. (if that line

m eets no surface, the function is undefined at (x, y)). If we project E onto

t he xy-plane we obtain a planar map, denoted by ~ = having the properties

s tated in the Introduction.

The combinatorial complexity ~b(E) o f the lower envelope of a

T heorem 2.1.

collection E of n surface patches that satisfy conditions (i)-(iv) is

O(n2. 2clf,i ~ ),

f or some constant c that depends on the degree b and the shape of the given

surfaces.

Proof. L et us denote by ~(n) the maximum value of O(E), taken over all

c ollections Z of n surface patches that satisfy conditions (i)-(iv) (for a fixed

d egree b).

N ew Bounds for Lower Envelopes in Three Dimensions 317

W e distinguish between i nner vertices o f the envelope, namely, vertices of the

e nvelope that are intersection points of the relative interiors of three surface

p atches in E, and the remaining outer vertices. C onsider first the outer vertices.

L emma 2.2. The maximum number of outer vertices is O(n24+2(n)), for some

constant q depending on the degree and shape of the given surfaces.

P roof L et us assume general position. There are O (n) o riginal vertices of

t he given patches, and O(nz) p oints of intersection between the boundary of one

s urface patch and the relative interior of another patch. Any other outer vertex is

f ormed either when the boundary of one surface patch passes above the boundary

o f another patch, or when an intersection curve of two patches passes above the

b oundary of a third patch. The number of outer vertices of the first kind is clearly

O(n2). A s to outer vertices of the second kind, fix a surface patch 0"~ Y,. We claim

t hat the total number of such vertices that lie on the boundary of the fixed 0" is

O(2q + 2(n)), for some constant q depending on the degree and shape of the surfaces.

T his is shown as in [5] and [6]: Let e be one of the (constant number of) algebraic

a rcs that form the boundary of 0", and let H be the vertical surface formed by

t he union of all vertical rays whose bottom endpoints lie on ~. For each

s urface 0 "1eE- {0"}, let 6i = ai n H. The properties that the surfaces satisfy

i mply that each 6~ is the union of a constant number of connected arcs, and that

e ach pair of such arcs intersect in at most some constant number, q, of points. It

is easily checked that each of the vertices under consideration must arise as a

breakpoint in the lower envelope of the arcs 6~, over one of the boundary pieces ct

o f a. Hence the total number of such endpoints is O(2q+2(n)) [ 11], as asserted.

S umming over all 0"~ E, the total number of outer vertices of the second kind is

O(n,~,q + 2(n)), []

H ence the number of outer vertices of all kinds is nearly quadratic and

s maller than the bound asserted in the theorem. The number of edges of

J r that do not contain any vertex at all is easily seen to be O(n2). T hus,

i f we establish the bound in the theorem for the number of inner vertices,

a nd apply Euler's formula for planar maps, we easily conclude that the same bound

a lso holds for the total complexity of

L et p be an inner vertex of the lower envelope, formed by the intersection

o f (the relative interiors of) three surface patches a~, 0"2, 0 3. By condition

(iiii, these patches intersect in at most one more point, so, with no loss of

g enerality, we can assume that there is no such intersection in the half-space

x > x(p), where x(p) is the x-coordinate of p. By the general position assumption,

w e may assume that p is not a singular point of any of these patches, and that

t hey meet each other transversally at p. Then, locally near p, the lower envelope

is approximated by the lower envelope of the three tangent planes to 0.~, 0.2, 0.3

a t p. In particular, each of the intersection curves ~12 = 0.~ ~ 0.2, 7~3 = a~ n 0"3,

723 = 0"2 n 0"3 contains a maximal connected x-monotone arc that emanates from

p a nd is hidden from below by the third surface. Let fl12, fl~3, fl23 d enote these

318 D. Halperin and M. Sharir

r espective arcs, and let z12, z13, z23 denote the other endpoints of these arcs. It

a lso follows that the positive span of the xy-projections of the three outgoing

t angent directions of fl12, 813,823 is the entire xy-plane: indeed, the three vectors

o ppositely oriented to these directions lie along the edges emerging from p of the

l ower envelope of the three tangent planes to the surfaces at p, and the x y-

p rojections of these vectors cannot lie in a single half-plane, as is easily checked.

H ence, at least one of these arcs, say 812, emanates from p in the positive

x -direction.

T wo cases can arise:

(a) z12 is an endpoint of(some connected x-monotone portion of) 712. In this

c ase we charge p to z12. Our assumptions imply that each Y12 has only

a c onstant number of such endpoints, so the total number of such

c harges will be proportional to the total number of intersection curves,

n amely, O(n2).

(b) Z12 is a point alon9 712 t hat lies directly above the boundary of tz3 (see Fig.

1). The difficulty is that z12 need not be vertically visible from &ra--there

m ay be many other surfaces lying below z12 and above the boundary (the

b oundary itself need not be on the lower envelope at this point, but this

d oes not concern us in the analysis given below). Suppose there are t such

s urfaces. We fix some threshold parameter k > 0, to be determined shortly,

a nd consider the following two subcases:

(i) t > k. Extend each surface r ~ E to a surface cr* by erecting an upward-

d irected vertical ray from each point on the boundary of a. Let E* denote

t he collection of these extended surfaces, and let J ( E * ) denote their

a rrangement. Our assumption implies that 812 contains at least t vertices

o f d(E*), and we charge p to the block of the first k of these vertices in

~ ~ /'12 /' ")'23

I

9 ..,. ~ ),%

Fig. 1. Case(b) of the proof: zl2 lies above the boundary of a3. The envelope is shown from below;

solid edges are visible whereas dashed edges are hidden from the envelope.

N ew Bounds for Lower Envelopes in Three Dimensions 319

t heir order from p to z12 along ill2. (Indeed, for any extended surface a*

t hat hides z12 from ~3a3, we trace fl12 from p toward z12; since a* does not

lie below p but lies below z12, there has to be a point along fl~2 where this

c urve intersects a*, yielding a vertex of ~r along fix2.) Each vertex of

d ( E * ) can be charged in this manner only a constant number of times: By

t he general position assumption, each inner vertex v is the intersection point

o f exactly three surfaces, and hence it is the meeting point of three

i ntersection curves (of pairs of the three surfaces). Evidently, for each of

t hese three curves, there are at most two vertices p lying on the curve and

o n the lower envelope for which the vertex v will be charged in this manner.

D efine the level o f a point x of 3-space in sO(E*) to be the number of

s urfaces of Z* that lie strictly below x (which is the same as the number of

o riginal surfaces in E that lie below x). It is easily checked that each of the

c harged vertices along fl12 is at level at most k (indeed, as we trace fl~2 from

p t o z~2, the level can change (by + 1) only when we cross one of these

v ertices).

O ur goal is thus to obtain an upper bound for the number of vertices

o f ~r that lie at level _ no (this is

New Bounds for Lower Envelopes in Three Dimensions 321

a lways possible by the results of [2]). For n > n 0, choose k = 2 (c- ~)Jo,~ .

fi

T he inequality (1) and the induction hypothesis imply that

~b(n) 1 +,,/2(1 + log A).

T his completes the proof of the theorem. []

3. The Envelope of Lines or Rays Over a Terrain

L et K be a polyhedral terrain in 3-space; that is, K is a continuous piecewise-linear

s urface intersecting each vertical line in exactly one point. Suppose K has n edges.

A l ine l is said to lie over K i f every point on l lies on or above K. Let ~ r denote

t he space of all lines that lie over K. The lower envelope o f ~K consists of those

l ines that touch at least one edge of K. Assuming general position of the edges of

K, a line in ~-a (or any line for that matter) can touch at most four edges of K.

K

O ur goal is to analyze the combinatorial complexity of the lower envelope. To

g et a feeling of what this lower envelope is, consider the four-dimensional space

~,r of parametric representation of lines in 3-space, where each point represents

o ne nondirected nonvertical line in 3-space. For each edge e of the terrain, the

p oints of ~r that represent lines in contact with e lie on a three-dimensional surface

p atch a e. The collection of all these surface patches defines a partitioning

o f the space U into cells of various dimensions. It is evident that the points

o f ~ corresponding to lines in LP occupy a single connected component C

K

o f ~,, whose boundary is determined by portions of the surfaces a e. We define the

c omplexity of the lower envelope of lines in ~'K to be the overall number of

l ower-dimensional cells on the boundary of C. To simplify matters (and with no

l oss of generality) we only count the number of its vertices, n amely, those

c orresponding to lines that touch four distinct edges of K (and we refer to them

a s "vertices" of L~K). We show:

T heorem 3.1. T he number of vertices of -~'r, as defined above, is 2c lCi~)for

O (n 3"

some absolute positive constant c.

322 D. Halperin and M. Sharir

P roof W e fix an edge e o of K, and bound the number of lines of ~'tK that

t ouch e o and three other edges of K, with the additional proviso that these

t hree other contact points all lie on one fixed side of the vertical plane passing

t hrough e 0. We then multiply this bound by the number n of edges to obtain a

b ound on the overall number of vertices of ZaK. We want to rephrase this problem

in terms of the lower envelope of a certain collection of surface patches in 3-space,

o ne patch for each other edge of K, to which we apply the results of the previous

s ection.

T he space ~eo of oriented lines that touch e o is three-dimensional: each

s uch line l can be specified by a triple (t, k,, where t is the point of contact

w ith eo (or, more precisely, the distance of that point from one designated

e ndpoint of eo), and k = tan 0, ~ = - c o t ~o, where (0, ~0) are the spherical co-

o rdinates of the direction of l, that is, 0 is the orientation of the xy-projection of

l, and q~ is the angle between l and the positive z-axis.

F or each edge e # eo of K let tre be the surface patch in L~a~0consisting

o f all points (t, k, ~) representing lines that touch e and are oriented from

eo to e. Note that if (t, k, 0 ~ ae, t hen ~ ' > ~ iff the line (t, k, passes below

e. It thus follows that a line l in ~e0 is a vertex of the lower envelope of &er

i f and only if l is a vertex of the lower envelope of the surfaces tr, in the

t k(-space, where the height of a point is its ~-coordinate. Hence, it remains

t o show that these surfaces satisfy conditions (i)-(iv) of the previous section,

a nd then the theorem will easily follow from Theorem 2.1.

C ondition (i) requires each ae to be monotone in the tk-direction, which

is immediate by definition; the algebraicity and the constant degree of these

s urfaces is also easy to verify. The vertical projection of o" onto the tk-plane

e

is easily seen to be the intersection of two double wedges--it is the set dual

t o the set of all lines in the xy-plane that intersect the xy-projections of e o

a nd e, under an appropriate (and standard) duality. Hence condition (ii) is

a lso satisfied. (Since this projection may be disconnected, we may want to

r eplace each tre by a constant number of subpatches, so that the tk-projection

o f each subpatch is a convex polygon of at most four sides.) Condition (iii),

w hich is the crucial one, follows from the observation that a point of intersection

o f the relative interiors of three surfaces ae,, O 'e2, O'e3, c orresponds to a line that

p asses through the four edges e 0, el, e2, and e3, and it it well known that there

c an be at most two such lines, assuming that these four edges are in general

p osition (see, e.g., [12]). Condition (iv) can be enforced by assuming the terrain K

t o be in general position. We argue, as in [17], that the maximum complexity of

t he envelope is achieved, up to a constant factor, when the terrain, and hence the

s urfaces defining the lower envelope of ~K, are in general position.

H ence, putting everything together and applying Theorem 2.1, we readily

o btain the bound asserted in the theorem. []

R emarks. (1) The bound of Theorem 3.1 has been independently obtained

b y Pellegrini [14J, using a different proof technique.

(2) Recently, de Berg [3] has shown a lower-bound construction of complexity

New Bounds for Lower Envelopes in Three Dimensions 323

-- .7

Fig. 2. An fl(n~) construction for the lower envelope of . ~ [3].

f~(n3) for the envelope of ~K, implying that our upper bound is almost tight

in the worst case. The construction consists of an almost fiat (horizontal) "hill"

w ith n/3 e dges, and two sets of n/3 s teep pyramids ("spikes") each, in front of the

hill; see Fig. 2 for an illustration. Clearly, this terrain has O(n) edges. If the

d imensions of the hill and spikes are assigned appropriately (in particular, the

e dges of the hill are long enough, and the spikes are sufficiently high), then a line

l ying over the terrain can touch an edge of the hill and (an edge of) one spike of

e ach row simultaneously, and this triple contact still leaves one degree of freedom

f or motion of the line along a small segment of each of the edges involved. This

h olds for every triple of an edge of the hill, and one spike from either row. Thus

we have ~ ( n 3) d istinct one-dimensional edges on the lower envelope of LP K.

T his construction induces [ ~(n 3) v ertices on the lower envelope of ~ which

a re obtained when a line touches two horizontal edges of the hill bounding

t he same face, and two spikes, one from each row.

W e can extend the result of Theorem 3.1 as follows. Let K be a terrain

as above. Let ~ r denote the space of all rays in 3-space with the property

t hat each point on such a ray lies on or above K. We define the lower

e nvelope of ~ x and its vertices in complete analogy to the case of Z~'K. By

i nspecting the proof of Theorem 3.1, it can be easily verified that it applies

e qually well to rays instead of lines. This is because, after fixing an edge e o,

e ach "ray-vertex" of ~ r under consideration, when extended into a full line,

b ecomes a "line-vertex" of ~x,, where K* is the portion of K cut off by a

h alf-space bounded by the vertical plane through e 0. Hence we obtain:

Corollary 3.2. The number of vertices of ~ r, as defined above, is also O(n 3" 2 c ~ ) .

T his corollary is needed in the following subsection.

324 D. Halperin and M. Sharir

3.1. The Number o f Orthooraphic Views of a Polyhedral Terrain

W e next apply Theorem 3.1 to obtain a bound on the number of topologic-

a lly different orthographic views (i.e., views from infinity) of a polyhedral terrain

K w ith n edges. This problem has been studied by de Berg e t al. 1,4,1. However,

t here is a certain technial error in their analysis (which we explain below). As

m entioned above, a correct form of the bound is O(n24(n)p(n)), w here #(n) is the

c omplexity of the ray-envelope of a terrain with n edges. In this subsection we

e xplain the connection between/~(n) and the bound on the number of views, and

u sing the result of the previous subsection, we conclude that this bound is

O(n 5 92r ~,/i~), for a constant c' slightly larger than the constant c in the bound

o f Corollary 3.2.

F ollowing the analysis of I-4,1, each orthographic view of K can be represented

a s a point on the sphere at infinity S~2. For each triple (e 1, e2, e3) of edges of K

w e consider the locus ~ 5.e~ of views for which these three edges appear to be

c oncurrent (that is, a line parallel to the viewing direction which touches these

t hree edges exists); each such locus is a curve along 6e2.

W e next replace each curve 7 = Yt 2.e~ as above by its maximal visible

p ortions; a point on y is said to be visible if the corresponding line that

t ouches the three edges el~ e2, e3 either lies over K or else penetrates below

K o nly at points that lie further away from its contacts with the edges e~,

e2, e3; in other words, we require the existence of a ray in the viewing direction

t hat touches et, e2, and e 3 but otherwise lies fully above K, As is easily verified,

e ach visible portion of 7 is delimited either at an original endpoint of 7 or at a

p oint whose corresponding ray is a vertex of ~ x . Hence, by Corollary 3.2, the total

n umber of the visible portions of the loci ? is O(n 3 92c1 ~ ) . We refer to these

v isible portions as a rcs of visible triple-contact views.

W e now continue along the lines of the analysis of [4,1. That is, we consider

t he arrangement of the arcs of visible triple-contact views, and observe that the

n umber of views that we seek to bound is proportional to the complexity of the

a rrangement of these arcs within 6~2. We next apply a result of Cole and Sharir

1,8-1, which, rephrased in the context under discussion, states that each meridian of

A 2 crosses at most k = O(nA4(n)) a rcs. As shown in 1'4,1, this implies that the

e

c omplexity of the arrangement of these arcs is O (Nk), w here N is the number of

a rcs. Hence we obtain

Corollary 3.3. 7he number of topologically different orthographic views of a

p olyhedral terrain with n edges is

O (n4,~,4(n) 9 2 el,/i~) = O(n 5. 2c'Jlos

f or c' slightly larger than c.

Remarks. (1) The technical error in 1,4] is that they considered the arrangement

o f the entire loci Yte,.e2.e~j, whereas, for the result of 1,8,1 to apply, one has to

c onsider, as done above, only their visible portions.

New Bounds for Lower Envelopesin Three Dimensions 325

(2) de Berg e t al. [ 4] also give a lower bound of f2(nSct(n)) f or the number

o f topologically different orthographic views of a polyhedral terrain with n

edges. Thus the above bound is almost tight in the worst case.

(3) The manuscript [4] also analyzes the number of topologically different

p erspective views of a polyhedral terrain. Again they make the technical error

n oted above, except that now they have to consider an arrangement of surface

p atches in 3-space rather than an arrangement of curves on the sphere at infinity.

As it turns out, what is needed here is a bound on the number of vertices of the

l ower envelope of the space g r of all line segments that lie over K, defined in

a nalogy with the spaces L~r and ~ r - Unfortunately, we do not know how to

e xtend our analysis to obtain nontrivial bounds for the case of d r . Nevertheless,

A garwal and Sharir have recently obtained an almost tight bound on the number

o f topologically different perspective views of a polyhedral terrain using a different

a pproach [1].

4. Conclusion

T he new bounds obtained in Section 2 for the complexity of the lower envelope

o f surface patches in 3-space push the frontier of research on these problems a

s tep further. In some intuitive sense the case studied in this paper is the next

s implest case for which subcubic bounds on the envelope complexity were not

k nown. So far we do not have other applications of our result, beyond the

a pplication to terrain visibility given in Section 3, but we anticipate that such

a pplications will be forthcoming.

T here are several open problems that our study raises. The most obvious

o ne is to close the remaining small gap between our upper bound and the

k nown near-quadratic lower bounds for the complexity of the envelope; we

c ontinue to conjecture that the correct bound is O(n2s(n)), f or some constant

s d epending on the degree and shape of the surfaces.

A nother open problem is to obtain nontrivial bounds on the complexity

o f the space gK, as defined above.

W e remark that the ideas used in the proof of Theorem 2.1 can be applied to

t he problem of bounding the complexity of a single cell in the free configuration

s pace of the motion-planning problem for an arbitrary polygonal object moving

( translating and rotating) in a two-dimensional polygonal environment, leading

t o near-quadratic bounds on that complexity. The dissertation 1-9] has studied

s everal special cases of this motion-planning problem, and obtained better, often

n ear-quadratic bounds in these cases, but no subcubic bounds were known for

t he general problem, as just stated. This extension of our results requires con-

s iderably more involved analysis than the one given in this paper, and it is

p resented in a companion paper [10].

F inally, the new technique developed in this paper is extended in the companion

p aper [17] to obtain similar almost tight bounds for the complexity of the envelope

in cases where the maximum number of intersection points between any triple of

s urface patches is a constant greater than two, as well as in higher dimensions.

3 26 D. Halperin and M. Sharir

S ee also the forthcoming book [18], where all these new results, as well as many

o ther related results and applications, are presented.

R eferences

1. P. K. Agarwal and M. Sharir, On the number of views of polyhedral terrains, Proc. 5th

Canadian Conf. on Computational Geometry, 1993, pp. 55-60.

2. P. K. Agarwal, M. Sharir, and P. Shor, Sharp upper and lower bounds for the length of general

D avenport-Schinzel sequences, J. Combin. Theory Ser. A 52 (1989), 228-274.

3. M. de Berg, Private communication, 1993.

4. M. de Berg, D. Halperin, M. Overmars, and M. van Kreveld, Sparse arrangements and the number

o f views of polyhedral scenes, Manuscript, 1991.

5. B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, A singly exponential stratification scheme

f or real semi-algebraic varieties and its applications, Theoretical Comput. Sci. 84 (1991), 77 105.

6. K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, Combinatorial complexity

b ounds for arrangements of curves and spheres, Discrete Comput. Geom. 5 (t990), 99-160.

7. K. Clarkson and P. Shor, Applications of random sampling in computational geometry, II. Discrete

Comput. Geom. 4 (1989), 387-421.

8. R. Cole and M. Sharir, Visibility problems for polyhedral terrains, J. S ymbolic Comput. 7 (1989),

1 1-30.

9. D. Halperin, Algorithmic Motion Planning via Arrangements of Curves and of Surfaces, Ph.D.

D issertation, Computer Science Department, Tel Aviv University, July 1992.

10. D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon

in a polygonal environment, Proc. 34th Ann. Symp. on Foundations o f Computer Science, 1993,

pp. 382-391.

11. S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path

c ompression schemes, Combinatorica 6 (1986), 151-177.

12. S. L. Kleiman and D. Laksov, Schubert calculus, Amer. Math. Monthly 79 (1972), 1061 1082.

13. J. Pach and M. Sharir, The upper envelope of piecewise linear functions and the boundary of a

r egion enclosed by convex plates: Combinatorial analysis, Discrete Comput. Geom. 4 (1989),

291-309.

14. M. Pellegrini, On lines missing polyhedral sets in 3-space, Proc. 9th A CM Syrup. on Computational

Geometry, 1993, pp. 19-28~

15. J. T. Schwartz and M. Sharir, On the two-dimensional Davenport-Schinzel problem, J. S ymbolic

Comput. 10 (1990), 371-393.

16. M. Sharir, On k-sets in arrangements of curves and surfaces, Discrete Comput. Geom. 6 (1991),

593-613.

17. M. Sharir, Almost tight upper bounds for lower envelopes in higher dimensions, this issue,

pp. 327-345.

18. M. Sharir and P. K. Agarwal, D avenport-Schinzel Sequences and Their Geometric Applications,

C ambridge University Press, Cambridge, to appear.

R eceived February 7, 1993, and in revised form December 13, 1993.

Contact this candidate