On the Union of ^-Round Ob jects in Three and Four Dimensions

On the Union ofκ-Round Objects

in Three and Four Dimensions?

Boris Aronov?Alon Efrat?Vladlen Koltun§Micha Sharir?

July1,2005

Abstract

A compact set c in R d isκ-round if for every point p∈?c there exists a closed

ball that contains p,is contained in c,and has radiusκdiam c.We show that,for any

?xedκ>0,the combinatorial complexity of the union of nκ-round,not necessarily

convex objects in R3(resp.,in R4)of constant description complexity is O(n2+ε)(resp.,

O(n3+ε))for anyε>0,where the constant of proportionality depends onε,κ,and

the algebraic complexity of the objects.The bound is almost tight in the worst case.

1Introduction

Given a set C of n geometric objects in R d,let U=U(C):= c∈C c denote their union, and let A=A(C)denote the arrangement[39]of the(boundaries of the)objects in C.The (combinatorial)complexity of U is de?ned to be the number of faces of A of all dimensions on the boundary?U of the union.The study of the complexity of the union of objects in

two dimensions has a long and rich history in computational and combinatorial geometry,

starting with the results of Kedem et al.[29]and Edelsbrunner et al.[19],who have shown

that,if the boundaries of any two distinct objects c1,c2∈C intersect at most twice(resp., three times),the maximum possible complexity of U isΘ(n)(resp.,Θ(nα(n)),whereα(·)is

the inverse Ackermann function).For the latter result to be meaningful,it is assumed that every c∈C is a region bounded between the x-axis and a Jordan arc whose endpoints lie on the x-axis,and where we only count intersections between these arcs.

When the object boundaries are allowed to intersect four or more times,the complexity

of U can easily reach?(n2),for instance when the objects form a grid of narrow strips.To

make such a construction possible,though,the objects have to be“long and skinny.”In an attempt to analyze the behavior of geometric objects in“real life”(e.g.,the prevailing geometric objects encountered in computer graphics,vision,manufacturing and robotics applications),various classes of realistic input models were introduced(see,e.g.,[14]),one of the most prominent among which is that of fat objects.The fat-object model addresses the observation that in some applications long and skinny objects are rarely encountered and objects with bounded aspect ratio are predominant.Under the assumption that the input objects are fat(see below for the several possible precise de?nitions),improved results were obtained for various algorithmic problems[3,4,7,13,22,27,28,30,33,34,40].As this list of applications indicates,there is a strong practical motivation to study the complexity of the union of fat objects,in addition to the intrinsic interest in the problem itself.

The union ofα-fat wedges,i.e.,wedges whose opening angle is at least some constant

α>0,has complexity O(n)[7,24];here and hereafter the implied constants depend on the fatness parameters.The union ofα-fat triangles,i.e.,triangles all of whose angles are at least some positive constantα,has complexity O(n log log n)[32,37].Extending the study into the realm of curved objects,Efrat and Sharir[23]have shown that the complexity of the union of n convex fat objects(i.e.,convex objects for which the ratio between the radii of the smallest enclosing and the largest enclosed disks is bounded by a global constant), each of constant description complexity,is O(n1+ε)for anyε>0.(An object has constant description complexity if it is a semi-algebraic set de?ned as a Boolean combination of a constant number of polynomial equalities and inequalities of constant maximum degree in a constant number of variables.)Efrat and Katz[21]have then shown that the union ofκ-curved(not necessarily convex)objects in the plane also has near-linear complexity.A planar object s is said to beκ-curved if,for any point p∈?s,there is a disk d?s that is incident to p and has radiusκtimes the diameter of s.(It is this de?nition that we extend to higher dimensions and study in the present paper.)Finally,extending both results,Efrat[20]has introduced a further generalization of fatness,with the property that the union complexity remains near-linear.See also[9,10,36,37]for other results concerning the union of objects in the plane.

Compared with this extensive research on the union of objects in R2,the situation in three

dimensions looks rather grim.Of course,the union of n thin plate-like objects that form a three-dimensional grid can have complexity?(n3).However,as in the plane,it is important, and motivated by a number of practical applications,to consider realistic input models,and in particular to study the complexity of the union of fat objects.A prevailing conjecture

2

is that this complexity(under an appropriate de?nition of fatness)is near-quadratic.Such a bound has however proved quite elusive to obtain for general fat objects,and this has been recognized as one of the major open problems in computational and combinatorial geometry[18,Problem4].

The complexity of the union of axis-parallel cubes is O(n2),and it drops to O(n)if the cubes have the same size[15].If the cubes are not axis-parallel but have equal(or“almost equal”)size,the complexity of their union is O(n2+ε)for anyε>0[35].A general sub-cubic bound on the complexity of the union of cubes in three dimensions is currently not known.Motivated by motion planning applications and the analysis of Voronoi diagrams, Aronov and Sharir[11]have proved a near-quadratic bound for the complexity of the union of Minkowski sums of disjoint convex polyhedra of overall complexity n with a common convex polyhedron of constant complexity.This re?nes a more general bound,obtained by Aronov et al.[12]for the case of the union of arbitrary convex polyhedra in3-space.Guided by similar motivations,Agarwal and Sharir[6]have shown that the union of Minkowski sums of disjoint polyhedra of overall complexity n with a ball has complexity O(n2+ε)for anyε>0.

The only rather general result on the complexity of the union of fat objects in3-space stems from the analysis technique of Agarwal and Sharir[6]and appears in their paper:The complexity of U(C)is O(n2+ε)for anyε>0if C consists of n convex objects of near-equal size,with C2-continuous boundaries,bounded mean curvature,and constant description complexity.

In d≥4dimensions,the results become even more scarce.The complexity of the union of n halfspaces(each bounded by a hyperplane)in R d is O(n?d/2?),as follows from the Upper Bound Theorem.The complexity of the union of n balls in d-space is O(n?d/2?),as follows by lifting them to hyperplanes in R d+1.Boissonnat et al.[15]present an upper bound of O(n?d/2?)for the union of n axis-parallel cubes in R d,which improves to O(n?d/2?)when the cubes have equal size.The union complexity of n convex bodies in R d of constant description complexity with a common interior point is O(n d?1+ε)for anyε>0,which follows from the results of Sharir[38]on the complexity of upper envelopes of(d?1)-variate functions(see also a re?ned bound for polyhedra in R3in[26]).Finally,Koltun and Sharir[31]extended the above-mentioned result of Agarwal and Sharir[6]to four dimensions and proved that the complexity of the union of n convex objects of near-equal size,with C2-continuous boundaries,bounded mean curvature,and constant description complexity in R4is O(n3+ε) for anyε>0.

Our results:We say that a set c?R d,d≥3,is an object if it is a compact connected set with nonempty interior.In a complete analogy with the de?nition ofκ-curved objects in two dimensions,a compact object c isκ-round(for a?xedκ>0)if for every point p∈?c there exists a closed ball B(p,c,κ)of radiusκdiam c,which contains p and is contained in c.We call B(p,c,κ)a witness ball for c at p.If c is convex,B(p,c,κ)is unique.The de?nition,though,allows c to be non-convex and to have re?ex edges and vertices,although c cannot have any convex edge or vertex.See Figure1.Recall that an object c has constant description complexity if it is a semi-algebraic set de?ned by a constant number of polynomial

3

equalities and inequalities of constant maximum degree in a constant number of variables.We refer to the largest of these constants as the algebraic complexity of c

.

κ-round κ-round not κ-round

Figure 1:Examples of (planar analogues of)κ-round and non-κ-round objects.

Our main result is the following:

Theorem 1.1.Let C be a set of n κ-round (not necessarily convex)objects of constant description complexity in R 3or in R 4.Then the combinatorial complexity of U (C )is O (n 2+ε)in R 3and O (n 3+ε)in R 4,for any ε>0,where the constant of proportionality depends on ε,κ,and the algebraic complexity of the objects in C .

The bound is nearly tight;for a construction see the concluding remarks.

We note that our analysis applies in any dimension d ≥3,except for its last step,where we reduce the problem to that of bounding the number of vertices of the sandwich region [39]between the upper envelope of a collection of (d ?1)-variate functions and the lower envelope of another such collection.Sharp bounds on the number of such sandwich vertices are known only for d =3and d =4,which is the only reason for our present inability to extend Theorem 1.1to d >4.

Our analysis extends the results of Agarwal and Sharir [6]and of Koltun and Sharir [31],as it allows the objects to be non-convex and to have drastically di?erent sizes.

We also note that our result implies that standard randomized divide-and-conquer tech-niques [2,11,12]can be used to construct the union of n κ-round objects with constant description complexity in 3-space in time O (n 2+ε)for any ε>0.

4

2The Complexity of the Union

2.1Fixing a Good Direction

Let C be a collection of nκ-round,not necessarily convex objects in R d,d≥3,of constant description complexity,and let U=U(C)denote their union.In what follows,we estimate

the combinatorial complexity of U by the number of vertices of?U,namely,the number of intersection points of d boundaries of objects of C that lie on?U.Let V=V(C)denote the set of these vertices.We assume general position of the objects in C,meaning,in particular,

that no d+1boundaries have a point in common,and no vertex of the union is a seam point(see the discussion below)of any of the boundary surfaces of its incident objects.This

involves no real loss of generality,since the maximum complexity of the union is attained for sets in general position,as follows,e.g.,from the discussion in[39].It is indeed su?cient to estimate the complexity of the union by the number of its vertices:Any face of?U that has

a vertex can be charged to one of its vertices,and the general position assumption implies that no vertex is charged more than2d?1times.The number of faces with no vertices can easily be shown to be O(n d?1),by charging each such face f to the intersection of at most d?1boundaries,so that f is incident to,or coincides with,a connected component of that intersection;the number of faces obtained in this manner from a?xed set of boundaries is

bounded by a function of d and of the algebraic complexity of the surfaces involved.

We recall and expand some additional notations.We consider objects in R d for any

?xed d≥3.(We re-emphasize that most of our analysis applies to any d≥3,and we will present it in this generality.)For an object c?R d,diam c denotes the diameter of c.Given 0<κ≤1/2,c isκ-round if through every point p∈?c there exists a closed witness ball B=B(p,c,κ)for c at p,which has radiusκdiam c,contains p and is contained in c.If p is a smooth point of?c,B(p,c,κ)is unique(see Lemma2.1).The term seam of c refers to the set of all non-smooth points(seam points)on?c.Each seam is a?nite union of algebraic arcs and singleton sets in three dimensions;in general it is a?nite union of relatively open (d?2)-dimensional algebraic cells.For any seam point p we de?ne B(p,c,κ)to be one of the balls that meets the above conditions.Recall that our general position assumptions require that no vertex of U(C)lies in the seam of any incident boundary.

Henceforth,we?x d andκ.The following fact is immediate from de?nitions.

Lemma2.1.If p is a smooth point of?c,then there is a unique hyperplaneπ=π(p,c) tangent to c at p and the ball B=B(p,c,κ)is tangent toπat p and thus uniquely determined by c,p∈?c,andκ.

Given a not necessarily smooth point p∈?c and a?xedα,where0<α<2,we say that direction n is good(α-good,to be precise)for c and p if the(undirected)line?(n,p) through p in direction n intersects the witness ball B(p,c,κ)in a segment of length at least ακdiam c,i.e.,at leastαtimes the radius of B(p,c,κ).A direction that is not good is bad. Lemma2.2.For a point p on the boundary of aκ-round object c,the measure of the set of bad directions for c and p can be upper bounded by an expressionμ(α)that depends only on α(and d)and not on the choice of p,c,orκ,and approaches zero asα→0.

5

Proof.As the de?nition of a bad direction is scale invariant,we scale c so that witness balls have unit radius.Fix a point p∈?c and let B=B(p,c,κ)be the corresponding unit witness ball.By de?nition of a bad direction,the line?through p in that direction has to be close enough to being tangent to B at p,so that its intersection pq with B has length less thanα.See Figure2.Letθbe the angle between?and the hyperplane tangent to B

Figure2:A bad direction for c and p;the cross section by the plane containing?and the center of B is shown.

at p.We must have sinθ<α/2for the direction to be bad,so the bad directions lie in the band of half-width sin?1(α/2)about the great sphere of directions tangent to B at p.The (d?1)-dimensional volume of this band is

μ(α):=v d?2 π/2+sin?1(α/2)

sin d?2?d?,

π/2?sin?1(α/2)

where v d?2is the volume of the(d?2)-dimensional unit sphere.Clearly,μ(α)satis?es the properties asserted in the lemma.

Consider a vertex v of U,incident to the boundaries of d objects c1,...,c d∈C.As a consequence of Lemma2.2,for each i,a random direction n will be bad for v and c i with probability at mostμ(α),so it will be good for v and all of the d incident boundaries(we will then say that n is good for v)with probability at least1?dμ(α),which we can assume to be at least1

Collins cells ,of dimensions 0,1,...,d ,where each full-dimensional cell can be written as the set of points satisfying a conjunction of inequalities of the following form 1

β?1

β?2(x 1)

β?3(x 1,x 2)

(1)

···β?d (x 1,...,x d ?1)≤x d ≤β+d (x 1,...,x d ?1),where all the functions β?j ,β+j are smooth algebraic functions of constant description com-

plexity.By the general position assumption,all vertices in V 0lie on the top or bottom boundary of some full-dimensional cell of each of their incident objects.(We note that the number of cells in Collins’cylindrical algebraic decomposition is usually quite large,albeit constant under our assumptions.For our analysis,any decomposition of c into cells of the above form will do.For example,one may use the vertical decomposition method,described,e.g.,in [39].)

We now construct the desired decomposition of ?c as the collection of the top and bottom boundaries of all the full-dimensional Collins cells of c .That is,for each such Collins cell σgiven by (2.2),we include in our decomposition the two patches σ?,σ+,given respectively by

β?1

β?2(x 1)

β?3(x 1,x 2)

···x d =β?d (x 1,...,x d ?1)or x d =β+d (x 1,...,x d ?1).

To simplify the notation,we continue to refer to these cell boundaries as the Collins cells of ?c .We distinguish between top Collins cells,those forming the top boundaries of the original full-dimensional cells,and bottom cells,those forming the bottom boundaries.

For any object c ∈C and any smooth point p ∈?c ,we say that p is good if the vertical direction is good for p and c .Fix an object c ∈C ,and let τbe a (d ?1)-dimensional Collins cell of ?c .Let G (τ)denote the set of all good points p that lie in the relative interior of τ.Recall that being good means that the vertical line through p ∈G (τ)enters c below p (if τis a top Collins cell)or above p (if τis a bottom Collins cell),and penetrates the (unique)corresponding witness ball B for a distance of at least αtimes its radius.Due to the constant description complexity of c and of τ,G (τ)consists of a constant number of connected components,each of constant description complexity.We view each of these components as the graph of a partial (d ?1)-variate function g .

Lemma 2.3.Let g be one of the partial functions de?ned above,and let D denote its domain of de?nition.Then the graph of g is “not too steep,”in the sense that any pair of points

x,x′∈D satisfy|g(x)?g(x′)|≤2ωdiam D/α,whereω≥1depends only on d and on the algebraic complexity of D.

Proof.By construction,the graphΓ=Γ(g)of g is a portion of a smooth algebraic surface delimited by a constant number of smooth algebraic arcs in three dimensions,or,in higher dimensions,by a constant number of lower-dimensional smooth algebraic patches of constant description complexity.At a point p of its relative interior,Γhas a well-de?ned tangent hyperplane that is“not too vertical,”as it forms an angleβ≥sin?1(α/2)with the vertical direction.This fact continues to hold at the boundary ofΓ,with the natural de?nition of a limit tangent hyperplane.In particular,the slope of any smooth curve on the closureˉΓofΓat any point p(i.e.,the value of dx d

1?(α/2)2

.

α

Connect the given pair of points x,x′∈D by a shortest pathγ?D.It is a concatenation of algebraic arcs and straight line segments;their number is at most a constant that depends on the algebraic complexity of D.Further subdivide these algebraic arcs into subarcs that are monotone in all coordinates.Again,the number of resulting subarcs is bounded by a function of the algebraic complexity of D.Each subarc?ts into a cube of edge length diam D. Therefore its L1-length,and therefore its Euclidean length too,is at most(d?1)diam D. Hence the Euclidean length|γ|ofγis at mostωdiam D,whereωis a constant that depends only on d and on the algebraic complexity of D.

To estimate|g(x)?g(x′)|,we integrate alongγ.“Lifting”each subarc ofγtoΓproduces a piecewise smooth curve of slope at most2/α,hence|g(x)?g(x′)≤2|γ|/α≤2ωdiam D/α, as claimed.

Lemma2.4.The good portion G(τ)of any Collins cellτof?c can be subdivided into patches, so that

(i)The x d-variation of each patch(i.e.,the length of its orthogonal projection to the x d-

axis)is at mostακdiam c/10.

(ii)The diameter of the projection of each patch to the hyperplane x d=0is at most α2κdiam c/(20ω),whereωis the parameter provided in Lemma2.3.

(iii)The number of patches is bounded by a function ofα,κ,d,and the algebraic complexity of the objects in C only.

Proof.Consider one of the(constant number of)connected components of G(τ)and let D denote its domain.Clearly,D is a semi-algebraic set of constant description complexity.The

statement in the proposition is scale invariant,so we assume D has diameter one.Overlay

√

D with a(d?1)-dimensional orthogonal grid of hyperplanes with stepα2κ/(20ω

comparable with that of D.De?ne a family of patchesπi,such that eachπi is the collection of points on G(τ)overδi.Each grid cell has diameterα2κ/(20ω)and thus,by Lemma2.3,the x d-coordinates of points on a patchπi vary by at mostακ/10.The number of patches is no

√

larger than O((α2κ/(20ω

Proof.The construction is carried out as follows:Lemma2.4provides a subdivision of G(τ)

into patches that will serve as the top caps of the pillars.Consider such a patchπi.The

pillar c i consists of points that lie vertically belowπi and above a horizontal base hyperplane lying at vertical distance2ακdiam c/5below the lowest point ofπi.Thus the pillars satisfy

(i)and(ii)by construction.By Lemma2.4,the vertical span of eachπi isακdiam c/10, and the diameter of its projection to the hyperplane x d=0isα2κdiam c/(20ω).These

properties,and the construction,imply properties(iii)–(v).The property that c i?c follows from the fact that each point ofπi is good.Finally,(vi)follows,since the vertical distance between a point on the top cap and on the bottom?at of a pillar is at least2ακdiam c/5

by(iv),while their horizontal distance is at mostα2κdiam c/(20ω)by(v),yielding a slope

of at least8ω/α.

Recall that we now consider only the subset V0of those vertices in V for which the vertical

direction is good.Any such vertex necessarily lies on the good part of the top or bottom boundary of each of the d objects that it is incident to.

We next consider the collection P+of all top pillars c i of all Collins cells of all original objects c∈C,and the analogous collection P?of bottom pillars,and put P:=P+∪P?.Any vertex q∈V0is also a vertex of the union U′:= P,so it su?ces to bound the complexity of U′,or,more precisely,to bound the number of vertices of U′that lie on the top or bottom cap of each of the pillars they are incident to.In fact,we can restrict our attention further to those vertices of U′that appear on d pillar caps and lie on the boundary of the original union U.Clearly,these are the only vertices of concern at this point.

For each pillarπ∈P,consider the projection h(π)ofπto the x d-axis.We obtain a set

H of intervals on the x d-axis,and construct a so-called hereditary segment tree T on H,as de?ned in[16].Each node w of T represents an interval I w along the x d-axis,and stores a list L w of long pillarsπ,whose projection to the x d-axis contains I w but does not fully

,where w0is the parent of w,and a list S w of short pillars,which are long in contain I w

some proper descendant of w;that is,their x d-span only partially overlaps I w.

Any vertex q∈V0of the type under consideration is incident to the caps of d pillars,all

stored as long in d nodes of T(not necessarily distinct)that lie on a common path to the

root,namely,the path from the leaf whose associated interval contains the x d-coordinate of q.Let w be the highest of these nodes(i.e.,the closest to the root).We count q at w.More precisely,the subproblem that we solve at w is to bound the number of vertices q of the union of L w∪S w,such that

(i)q lies in the caps of all incident pillar boundaries,

(ii)the x d-coordinate of q lies in I w,

(iii)q is incident to at least one long pillar in L w,and

(iv)q∈?U.

Deriving this bound forms the focus of the following subsection.The sum of these bounds, over all nodes w of T,yields a bound for|V0|and is thus the quantity we wish to bound.

10

2.3Bounding the Union Complexity of Pillars

Let σw denote the horizontal slab R d ?1×I w .Suppose that one of the pillars incident to q is a long top pillar πin L w whose cap contains q .By construction,any point in σw lying vertically below the cap of πis contained in π.Hence,q is a point on the upper envelope of the caps of the top pillars in L w .Symmetrically,if π′is a long bottom pillar in L w whose cap contains q ,then q is a point on the lower envelope of the caps of the bottom pillars in L w .

Suppose next that q is incident to a short top pillar π′in S w whose top cap is incident to q .Since π′is short,its bottom ?at may lie in the interior of σw .A similar situation may arise when π′is a short bottom pillar whose bottom cap is incident to q .Therefore,at ?rst sight it appears that short pillars cannot be handled by just considering vertices that lie on their upper or lower envelopes.However,the following two lemmas show that the relevant vertices can be captured along envelopes of certain “canonical”subsets of short pillars.Lemma 2.6.Let π′be a short top pillar,whose top cap is incident to a vertex q of the union U that also lies on the top cap of a long top pillar π.Then each point in σw vertically below π′is contained in the interior of the original union U and thus cannot contain a vertex of U .Symmetrically,if π′is a short bottom pillar,whose bottom cap is incident to a vertex of the union that also lies on the bottom cap of a long bottom pillar,then each point in σw vertically above π′is contained in the original union U .

Proof.It is enough to address the case of top pillars.Let s ∈σw be a point that lies vertically below (the ?at bottom of)π′.Then the angle ?between qs and the x d -axis is rather small.Speci?cally,by Corollary 2.5(vi),we have tan ?<α/(8ω)<α/8(since ω≥1).Refer to Figure

4.

σw

Figure 4:The ?gure depicts a short top pillar π′whose top cap is incident to a vertex q of the union U that also lies on the top cap of a long top pillar π.Every point s lying within σw below π′must be contained in the interior of U .

Let c be the object that contains π.Consider the witness ball B =B (q,c,κ)for c at q .We claim that s ∈B .Indeed,since πis long in w ,we have,by Corollary 2.5(iv),|I w |≤ακdiam c/2.Hence the di?erence between the x d -coordinates of q and s is less than α/2times the radius of B .Recall that q lies on G +(c )and thus it is the top endpoint of a vertical chord of B of length at least αtimes the radius.It therefore follows that s lies

11

above the center of B.Refer to Figure5,which depicts the two-dimensional vertical cross section of B through q and the center o of B.Suppose that the length of the vertical chord

Figure5:Illustrating the proof that the point s lies inside B.The?gure depicts a vertical 2-dimensional cross section of B through o and q;s does not necessarily lie in that cross section.

of B through q is exactlyβtimes the radius of B,β≥α,and use the notation in the?gure to conclude that

1? β/2>β/4≥α/4.

tan?bqa=

However,we have shown that tan?sqa<α/8.This,and the fact that s lies above o,is easily seen to imply that s lies in the interior of B,as asserted,which clearly completes the proof of the lemma.

Remark.If,as depicted in Figure4,π′“hangs over”the vertical boundary ofπ,the point s may lie outside the union of the pillars(e.g.,whenπis an extreme pillar of c).However, s still lies within the interior of the union U of the original objects,as we have just shown. Lemma2.7.Letπ′be a short bottom pillar,whose bottom cap is incident to a vertex q of U that also lies on the top cap of a long top pillarπ,and let s be a point inσw vertically aboveπ′.Then s cannot lie on the top cap of any long top pillar.

Symmetrically,letπ′be a short top pillar,whose top cap is incident to a vertex q of U that also lies on the bottom cap of a long bottom pillar,and let s be a point inσw vertically below π′.Then s cannot lie on the bottom cap of any long bottom pillar.

Proof.It is su?cient to consider only the former scenario.The proof is very similar to that of the preceding lemma.Suppose to the contrary that s does lie on the top cap of another long pillarπ′′,contained in an original object c′′∈C.See Figure6.One can show,arguing in much the same way as above,that the angle?between sq and the x d-direction satis?es tan?<α/8.Let B=B(s,c′′,κ)be the witness ball for c′′at s.Then,repeating the calculation illustrated in Figure5,one concludes that q must lie in the interior of B,which is impossible.

In view of Lemma2.6,we can take each short top pillarπ′,whose top cap is incident to a vertex that also lies on the top cap of a long top pillar,and extend it all the way to the

12

σw

Figure6:No point s withinσw can lie(a)above a short bottom pillarπ′whose bottom cap

is incident to a vertex q of the union U that also lies on the top cap of a long top pillar π,and(b)on the top cap of another long top pillar.Only a portion of the long pillarπis

depicted;the full pillar crosses the slab from top to bottom.

bottom ofσw,without covering any vertex of the union under consideration.Symmetrically,

any short bottom pillar whose bottom cap is incident to a vertex that also lies on the

bottom cap of a long bottom pillar,can be extended all the way to the top ofσw,without covering any vertex of the union under consideration.Exploiting Lemma2.7is done a little

di?erently—see below.

Denote by L+w the set of long top pillars in L w,and by L?w the set of long bottom pillars in

L w.Denote by S+w the set of extended short top pillars in S w,and by S?w the set of extended

short bottom pillars in S w;only those short pillars that satisfy the conditions in Lemma2.6 are included in S+w and S?w.

Let q∈σw be a vertex of the union that lies on the cap of at least one long pillar in L w. We consider the following cases:

Case A:q is incident only to top caps of(long or extended short)top pillars.In this case, the preceding analysis implies that q is a vertex of the upper envelope of the top caps of the

pillars in L+w∪S+w.Symmetrically,if q is incident only to bottom caps of(long or extended short)bottom pillars,then q is a vertex of the lower envelope of the bottom caps of the

pillars in L?w∪S?w.

Case B:q is incident to at least one top cap of a long top pillar in L+w,and to at least one

bottom cap of a long bottom pillar in L?w.Here,by Lemma2.6,any short pillar incident to q

can be extended up or down,as appropriate,which is easily seen to imply that q is a vertex of the sandwich region[5,39]between the upper envelope of the caps of pillars in L+w∪S+w and the lower envelope of the caps of pillars in L?w∪S?w.

Case C:q is incident to at least one top cap of a long top pillar in L+w,to no bottom cap

of any long bottom pillar in L?w,and to some top or bottom caps of short pillars.Let V?denote the set of these vertices.If q is incident to the bottom caps of some short bottom pillars,then,in view of Lemma2.7,we can extend any such pillarπ′upwards to the ceiling ofσw,without covering any other vertex of V?.Let?S?w denote the set of short bottom pillars π′that contain such a point q on their bottom caps.Hence,in this case q is a vertex of the

13

sandwich region between the upper envelope of the top caps of pillars in L+w∪S+w and the lower envelope of the bottom caps of pillars in?S?w.The symmetric case,in which the roles

of L+w and L?w are interchanged,is analyzed in much the same way,and implies that q is a vertex of the sandwich region between the lower envelope of the bottom caps of pillars in L?w∪S?w and the upper envelope of the top caps of pillars in an analogously de?ned set?S+w.

Hence,in all three cases,q is a vertex of either an upper envelope,or a lower envelope,or the sandwich region between two envelopes,of caps of pillars in certain combinations of the sets L+w,L?w,S+w,S?w,?S+w,?S?w.As argued above,the caps of the pillars in these sets all have constant description complexity.Hence,using the results in[1,25,31,38],it follows that,for d=3or4,the number of vertices q under consideration insideσw is

O (|L+w|+|L?w|+|S+w|+|S?w|+|?S+w|+|?S?w|)d?1+ε

for anyε>0,where the constant of proportionality depends onε,κ,d,and on the algebraic complexity of the objects in C.(Note that this is the only stage in the analysis where we restrict the dimension d.)

We sum this bound over all nodes w of the segment tree T.By the properties of hereditary segment trees[16],we have

(|L+w|+|L?w|+|S+w|+|S?w|+|?S+w|+|?S?w|)=O(|P|log|P|),

w

where P is,as above,the set of all pillars.By construction,|P|=O(n),where the constant of proportionality depends onκ,d,and the algebraic complexity of the objects in C.This implies that

(|L+w|+|L?w|+|S+w|+|S?w|+|?S+w|+|?S?w|)d?1+ε=O(n d?1+ε),

w

for anyε>0,and so the proof of Theorem1.1is complete.

Remarks.(1)As already mentioned,the analysis holds in any dimension,except for the lack of a sharp bound on the complexity of the sandwich region between envelopes in?ve and higher dimensions.The availability of such a bound would immediately imply the extension of Theorem1.1to the respective dimension.

(2)The bound in Theorem1.1is nearly tight,in the following sense.For anyε>0,there exists a family of nκ-round objects in R d,d≥3,of constant description complexity,whose

union has complexity?(n d?1),withκ=1/(2(1+ε))and implied constant independent of

√

ε.Here is one such construction.Put m:=n/(d?1)and h:=

and touching p,so the roundness factorκof c is(h/2ε)/(h+h/ε)=1/(2(1+ε)),as claimed. Moreover,all objects are tangent to the hyperplane x d=h and their intersections with it form a(d?1)-dimensional grid of complexityΘ(m d?1)=Θ(n d?1).Thus in particular the union of the objects has complexity?(n d?1).Degeneracies can be removed by slightly perturbing the individual objects without reducing the complexity of the union.This construction is closely related to the one presented in[8].

Acknowledgments

The authors would like to thank Carola Wenk for fruitful discussions.

References

[1]P.K.Agarwal,O.Schwarzkopf,and M.Sharir,The overlay of lower envelopes and its

applications,Discrete Comput.Geom.15(1996),1–13.

[2]P.K.Agarwal,B.Aronov,and M.Sharir,Motion planning for a convex polygon in a

polygonal environment,Discrete Comput.Geom.22(1999),201–221.

[3]P.K.Agarwal,E.F.Grove,T.M.Murali,and J.S.Vitter,Binary space partitions for fat

rectangles,SIAM https://www.doczj.com/doc/fd582849.html,put.29(2000),1422–1448.

[4]P.K.Agarwal,M.Katz,and M.Sharir,Computing depth order and related problems,

Comput.Geom.Theory Appl.5(1995),187–206.

[5]P.K.Agarwal and M.Sharir,Arrangements of surfaces in higher dimensions,in Hand-

book of Computational Geometry,J.R.Sack and J.Urrutia(Eds.),North-Holland,2000, pp.49–119.

[6]P.K.Agarwal and M.Sharir,Pipes,cigars,and kreplach:The union of Minkowski sums

in three dimensions,Discrete Comput.Geom.24(2000),645–685.

[7]H.Alt,R.Fleischer,M.Kaufmann,K.Mehlhorn,S.N¨a her,S.Schirra,and C.Uhrig,

Approximate motion planning and the complexity of the boundary of the union of simple geometric?gures,Algorithmica8(1992),391–406.

[8]B.Aronov,A lower bound on Voronoi diagram complexity,Inform.Process.Lett.83

(2002),183–185.

[9]B.Aronov,A.Efrat,D.Halperin,and M.Sharir,A subquadratic bound on the number

of regular vertices of the union of Jordan regions,Discrete Comput.Geom.25(2001), 203–220.

[10]B.Aronov and M.Sharir,The common exterior of convex polygons in the plane,Com-

put.Geom.Theory Appl.8(1997),139–149.

15

[11]B.Aronov and M.Sharir,On translational motion planning of a convex polyhedron in

3-space,SIAM https://www.doczj.com/doc/fd582849.html,put.26(1997),1785–1803.

[12]B.Aronov,M.Sharir,and B.Tagansky,The union of convex polyhedra in three dimen-

sions,SIAM https://www.doczj.com/doc/fd582849.html,put.26(1997),1670–1688.

[13]M.de Berg,Linear size binary space partitions for uncluttered scenes,Algorithmica28

(2000),353–366.

[14]M.de Berg,M.J.Katz,A.F.van der Stappen,and J.Vleugels,Realistic input models

for geometric algorithms,Algorithmica34(2002),81–97.

[15]J.-D.Boissonnat,M.Sharir,B.Tagansky,and M.Yvinec,Voronoi diagrams in higher

dimensions under certain polyhedral distance functions,Discrete Comput.Geom.19 (1998),473–484.

[16]B.Chazelle,H.Edelsbrunner,L.Guibas,and M.Sharir,Algorithms for bichromatic

line segment problems and polyhedral terrains,Algorithmica11(1994),116–132. [17]G.E.Collins,Quanti?er elimination for real closed?elds by cylindrical algebraic decom-

position,In Proceedings of the Second GI Conference on Automata Theory and Formal Languages,134–183.Springer Lecture Notes in Computer Science33,1975.

[18]E.D.Demaine,J.S.B.Mitchell,and J.O’Rourke,The Open Problems Project,http:

//https://www.doczj.com/doc/fd582849.html,/?orourke/TOPP/.

[19]H.Edelsbrunner,L.J.Guibas,J.Pach,R.Pollack,R.Seidel,and M.Sharir,Arrange-

ments of curves in the plane:Topology,combinatorics,and algorithms,https://www.doczj.com/doc/fd582849.html,put.

Sci.92(1992),319–336.

[20]A.Efrat,The complexity of the union of(α,β)-covered objects,SIAM https://www.doczj.com/doc/fd582849.html,put.,34

(2005),775–787.

[21]A.Efrat and M.Katz,On the union ofκ-curved objects,Comput.Geom.Theory Appl.

14(1999),241–254.

[22]A.Efrat,M.J.Katz,F.Nielsen,and M.Sharir,Dynamic data structures for fat objects

and their applications,Comput.Geom.Theory Appl.15(2000),215–227.

[23]A.Efrat and M.Sharir,The complexity of the union of fat objects in the plane,Discrete

Comput.Geom.23(2000),171–189.

[24]A.Efrat,G.Rote,and M.Sharir,On the union of fat wedges and separating a collection

of segments by a line,Comput.Geom.Theory Appl.3(1993),277–288.

[25]D.Halperin and M.Sharir,New bounds for lower envelopes in three dimensions with

applications to visibility of terrains,Discrete Comput.Geom.12(1994),313–326. [26]D.Huttenlocher,K.Kedem,and M.Sharir,The upper envelope of Voronoi surfaces and

its applications,Discrete Comput.Geom.9(1993),267–291.

16

[27]M.Katz,3-D vertical ray shooting and2-D point enclosure,range searching,and arc

shooting amidst convex fat objects,Comput.Geom.Theory Appl.8(1997),299–316.

[28]M.Katz,M.Overmars,and M.Sharir,E?cient output sensitive hidden surface removal

for objects with small union size,Comput.Geom.Theory Appl.2(1992),223–234. [29]K.Kedem,R.Livne,J.Pach,and M.Sharir,On the union of Jordan regions and

collision-free translational motion amidst polygonal obstacles,Discrete Comput.Geom.

1(1986),59–71.

[30]M.van Kreveld,On fat partitioning,fat covering,and the union size of polygons,Com-

put.Geom.Theory Appl.9(1998),197–210.

[31]V.Koltun and M.Sharir,The partition technique for overlays of envelopes,SIAM J.

Comput.32(2003),841–863.

[32]J.Matouˇs ek,J.Pach,M.Sharir,S.Sifrony,and E.Welzl,Fat triangles determine linearly

many holes,SIAM https://www.doczj.com/doc/fd582849.html,put.23(1994),154–169.

[33]M.H.Overmars,Point location in fat subdivisions,Inform.Process.Lett.44(1992),

261–265.

[34]M.H.Overmars and A.F.van der Stappen,Range searching and point location among

fat objects,J.Algorithms21(1996),629–656.

[35]J.Pach,I.Safruti,and M.Sharir,The union of congruent cubes in three dimensions,

Discrete Comput.Geom.30(2003),133–160.

[36]J.Pach and M.Sharir,On the boundary of the union of planar convex sets,Discrete

Comput.Geom.21(1999),321–328.

[37]J.Pach and G.Tardos,On the boundary complexity of the union of fat triangles,SIAM

https://www.doczj.com/doc/fd582849.html,put.31(2003),1745–1760.

[38]M.Sharir,Almost tight upper bounds for lower envelopes in higher dimensions,Discrete

Comput.Geom.12(1994),327–345.

[39]M.Sharir and P.K.Agarwal,Davenport-Schinzel Sequences and Their Geometric Ap-

plications,Cambridge University Press,New York,1995.

[40]A.F.van der Stappen,D.Halperin,and M.H.Overmars,The complexity of the free

space for a robot moving amidst fat obstacles,Comput.Geom.Theory Appl.3(1993), 353–373.

17

五年级上册成语解释及近义词反义词和造句大全.doc

五年级上册成语解释及近义词反义词和造句大全 囫囵吞枣；【解释】：囫囵：整个儿。把枣整个咽下去，不加咀嚼，不辨味道。比喻对事物不加分析考虑。【近义词】：不求甚解【反义词】融会贯穿[造句];学习不能囫囵吞枣而是要精益求精 不求甚解；bùqiúshènjiě【解释】：甚：专门，极。只求明白个大概，不求完全了解。常指学习或研究不认真、不深入【近义词】：囫囵吞枣【反义词】：精益求精 造句；1；在学习上，我们要理解透彻，不能不求甚解 2；学习科学文化知识要刻苦钻研，深入领会，不能粗枝大叶，不求甚解。 千篇一律；【解释】：一千篇文章都一个样。指文章公式化。也比喻办事按一个格式，专门机械。 【近义词】：千人一面、如出一辙【反义词】：千差万别、形形色色 造句；学生旳作文千篇一律，专门少能有篇与众不同旳，这确实是平常旳练习太少了。 倾盆大雨；qīngpéndàyǔ【解释】：雨大得象盆里旳水直往下倒。形容雨大势急。 【近义词】：大雨如柱、大雨滂沱【反义词】：细雨霏霏牛毛细雨 造句；3月旳天说变就变，瞬间下了一场倾盆大雨。今天下了一场倾盆大雨。 坚决果断；áobùyóuyù：意思；做事果断，专门快拿定了主意，一点都不迟疑，形容态度坚决 近义词；不假思索斩钉截铁反义词；犹豫不决 造句；1看到小朋友落水，司马光坚决果断地搬起石头砸缸。2我坚决果断旳承诺了她旳要求。 饥肠辘辘jīchánglùlù【近义词】：饥不择食【反义词】：丰衣足食 造句；1我放学回家已是饥肠辘辘。2那个饥肠辘辘旳小孩差不多两天没吃饭了 滚瓜烂熟gǔnguālànshóu〔shú)【解释】：象从瓜蔓上掉下来旳瓜那样熟。形容读书或背书流利纯熟。【近义词】：倒背如流【反义词】：半生半熟造句；1、这篇课文我们早已背得滚瓜烂熟了 流光溢彩【liúguāngyìcǎi】解释；光影，满溢旳色彩，形容色彩明媚 造句：国庆节，商场里装饰旳流光溢彩。 津津有味；jīnjīnyǒuwèi解释：兴趣浓厚旳模样。指吃得专门有味道或谈得专门有兴趣。 【近义词】：兴致勃勃有滋有味【反义词】：索然无味、枯燥无味 造句；1今天旳晚餐真丰富，小明吃得津津有味。 天长日久；tiānchángrìjiǔ【解释】：时刻长，生活久。【近义词】：天长地久【反义词】：稍纵即逝 造句：小缺点假如不立即改掉, 天长日久就会变成坏适应 如醉如痴rúzuìrúchī【解释】：形容神态失常，失去自制。【近义词】：如梦如醉【反义词】：恍然大悟造句；这么美妙旳音乐，我听得如醉如痴。 浮想联翩【fúxiǎngliánpiān解释】：浮想：飘浮不定旳想象；联翩：鸟飞旳模样，比喻连续不断。指许许多多旳想象不断涌现出来。【近义词】：思绪万千 造句；1他旳话让人浮想联翩。2:这幅画饱含诗情，使人浮想联翩，神游画外，得到美旳享受。 悲欢离合bēihuānlíhé解释；欢乐、离散、聚会。泛指生活中经历旳各种境遇和由此产生旳各种心情【近义词】：酸甜苦辣、喜怒哀乐【反义词】：平淡无奇 造句；1人一辈子即是悲欢离合,总要笑口常开,我们旳生活才阳光明媚. 牵肠挂肚qiānchángguàdù【解释】：牵：拉。形容十分惦念，放心不下 造句；儿行千里母担忧，母亲总是那个为你牵肠挂肚旳人 如饥似渴rújīsìkě：形容要求专门迫切，仿佛饿了急着要吃饭，渴了急着要喝水一样。 造句；我如饥似渴地一口气读完这篇文章。他对知识旳如饥似渴旳态度造就了他今天旳成功。 不言而喻bùyánéryù【解释】：喻：了解，明白。不用说话就能明白。形容道理专门明显。 【近义词】：显而易见【反义词】：扑朔迷离造句；1珍惜时刻，好好学习，那个道理是不言而喻旳 与众不同；yǔzhòngbùtóng【解释】：跟大伙不一样。 〖近义词〗别出心裁〖反义词〗平淡无奇。造句； 1从他与众不同旳解题思路中，看出他专门聪慧。2他是个与众不同旳小孩

on the contrary的解析

On the contrary Onthecontrary, I have not yet begun. 正好相反，我还没有开始。 https://www.doczj.com/doc/fd582849.html, Onthecontrary, the instructions have been damaged. 反之，则说明已经损坏。 https://www.doczj.com/doc/fd582849.html, Onthecontrary, I understand all too well. 恰恰相反，我很清楚 https://www.doczj.com/doc/fd582849.html, Onthecontrary, I think this is good. ⑴我反而觉得这是好事。 https://www.doczj.com/doc/fd582849.html, Onthecontrary, I have tons of things to do 正相反，我有一大堆事要做 Provided by jukuu Is likely onthecontrary I in works for you 反倒像是我在为你们工作 https://www.doczj.com/doc/fd582849.html, Onthecontrary, or to buy the first good. 反之还是先买的好。 https://www.doczj.com/doc/fd582849.html, Onthecontrary, it is typically american. 相反，这正是典型的美国风格。 222.35.143.196 Onthecontrary, very exciting.

恰恰相反，非常刺激。 https://www.doczj.com/doc/fd582849.html, But onthecontrary, lazy. 却恰恰相反，懒洋洋的。 https://www.doczj.com/doc/fd582849.html, Onthecontrary, I hate it! 恰恰相反，我不喜欢！ https://www.doczj.com/doc/fd582849.html, Onthecontrary, the club gathers every month. 相反，俱乐部每个月都聚会。 https://www.doczj.com/doc/fd582849.html, Onthecontrary, I'm going to work harder. 我反而将更努力工作。 https://www.doczj.com/doc/fd582849.html, Onthecontrary, his demeanor is easy and nonchalant. 相反，他的举止轻松而无动于衷。 https://www.doczj.com/doc/fd582849.html, Too much nutrition onthecontrary can not be absorbed through skin. 太过营养了反而皮肤吸收不了. https://www.doczj.com/doc/fd582849.html, Onthecontrary, I would wish for it no other way. 正相反，我正希望这样 Provided by jukuu Onthecontrary most likely pathological. 反之很有可能是病理性的。 https://www.doczj.com/doc/fd582849.html, Onthecontrary, it will appear clumsy. 反之，就会显得粗笨。 https://www.doczj.com/doc/fd582849.html,

The way常见用法

The way 的用法 Ⅰ常见用法： 1)the way+ that 2)the way + in which（最为正式的用法） 3)the way + 省略（最为自然的用法） 举例：I like the way in which he talks. I like the way that he talks. I like the way he talks. Ⅱ习惯用法： 在当代美国英语中，the way用作为副词的对格，“the way+ 从句”实际上相当于一个状语从句来修饰整个句子。 1)The way =as I am talking to you just the way I’d talk to my own child. He did not do it the way his friends did. Most fruits are naturally sweet and we can eat them just the way they are—all we have to do is to clean and peel them. 2）The way= according to the way/ judging from the way The way you answer the question, you are an excellent student. The way most people look at you, you’d think trash man is a monster. 3）The way =how/ how much No one can imagine the way he missed her. 4）The way =because

悲惨的近义词反义词和造句

悲惨的近义词反义词和造句 导读：悲惨的近义词 悲凉(注释:悲哀凄凉：～激越的琴声。) 悲惨的反义词 幸福(注释:个人由于理想的实现或接近而引起的一种内心满足。追求幸福是人们的普遍愿望，但剥削阶级把个人幸福看得高于一切，并把个人幸福建立在被剥削阶级的痛苦之上。无产阶级则把争取广大人民的幸福和实现全人类的解放看作最大的幸福。认为幸福不仅包括物质生活，也包括精神生活;个人幸福依赖集体幸福，集体幸福高于个人幸福;幸福不仅在于享受，而主要在于劳动和创造。) 悲惨造句 1.一个人要发现卓有成效的真理，需要千百个人在失败的探索和悲惨的错误中毁掉自己的生命。 2.贝多芬的童年尽管如是悲惨，他对这个时代和消磨这时代的地方，永远保持着一种温柔而凄凉的回忆。 3.卖火柴的小女孩在大年夜里冻死了，那情景十分悲惨。 4.他相信，他们每个人背后都有一个悲惨的故事。 5.在那次悲惨的经历之后，我深信自己绝对不是那种可以离家很远的人。 6.在人生的海洋上，最痛快的事是独断独航，但最悲惨的却是回头无岸。 7.人生是艰苦的。对不甘于平庸凡俗的人那是一场无日无夜的斗

争，往往是悲惨的、没有光华的、没有幸福的，在孤独与静寂中展开的斗争。……他们只能依靠自己，可是有时连最强的人都不免于在苦难中蹉跎。罗曼·罗兰 8.伟大的心胸，应该表现出这样的气概用笑脸来迎接悲惨的厄运，用百倍的勇气来应付开始的不幸。鲁迅人在逆境里比在在顺境里更能坚强不屈。遇厄运时比交好运时容易保全身心。 9.要抓紧时间赶快生活，因为一场莫名其妙的疾病，或者一个意外的悲惨事件，都会使生命中断。奥斯特洛夫斯基。 10.在我一生中最悲惨的一个时期，我曾经有过那类的想法：去年夏天在我回到这儿附近的地方时，这想法还缠着我;可是只有她自己的亲自说明才能使我再接受这可怕的想法。 11.他们说一个悲惨的故事是悲剧，但一千个这样的故事就只是一个统计了。 12.不要向诱惑屈服，而浪费时间去阅读别人悲惨的详细新闻。 13.那起悲惨的事件深深地铭刻在我的记忆中。 14.伟大的心胸，应该用笑脸来迎接悲惨的厄运，用百倍的勇气来应付一切的不幸。 15.一个人要发现卓有成效的真理，需要千百万个人在失败的探索和悲惨的错误中毁掉自己的生命。门捷列夫 16.生活需要爱，没有爱，那些受灾的人们生活将永远悲惨;生活需要爱，爱就像调味料，使生活这道菜充满滋味;生活需要爱，爱让生活永远充满光明。

英语造句

一般过去式 时间状语：yesterday just now (刚刚) the day before three days ag0 a week ago in 1880 last month last year 1. I was in the classroom yesterday. I was not in the classroom yesterday. Were you in the classroom yesterday. 2. They went to see the film the day before. Did they go to see the film the day before. They did go to see the film the day before. 3. The man beat his wife yesterday. The man didn’t beat his wife yesterday. 4. I was a high student three years ago. 5. She became a teacher in 2009. 6. They began to study english a week ago 7. My mother brought a book from Canada last year. 8.My parents build a house to me four years ago . 9.He was husband ago. She was a cooker last mouth. My father was in the Xinjiang half a year ago. 10.My grandfather was a famer six years ago. 11.He burned in 1991

The way的用法及其含义(二)

The way的用法及其含义（二） 二、the way在句中的语法作用 the way在句中可以作主语、宾语或表语： 1.作主语 The way you are doing it is completely crazy.你这个干法简直发疯。 The way she puts on that accent really irritates me. 她故意操那种口音的样子实在令我恼火。The way she behaved towards him was utterly ruthless. 她对待他真是无情至极。 Words are important, but the way a person stands, folds his or her arms or moves his or her hands can also give us information about his or her feelings. 言语固然重要,但人的站姿,抱臂的方式和手势也回告诉我们他(她)的情感。 2.作宾语 I hate the way she stared at me.我讨厌她盯我看的样子。 We like the way that her hair hangs down.我们喜欢她的头发笔直地垂下来。 You could tell she was foreign by the way she was dressed. 从她的穿著就可以看出她是外国人。 She could not hide her amusement at the way he was dancing. 她见他跳舞的姿势，忍俊不禁。 3.作表语 This is the way the accident happened.这就是事故如何发生的。 Believe it or not, that's the way it is. 信不信由你, 反正事情就是这样。 That's the way I look at it, too. 我也是这么想。 That was the way minority nationalities were treated in old China. 那就是少数民族在旧中

(完整版)the的用法

定冠词the的用法： 定冠词the与指示代词this ,that同源,有“那(这)个”的意思,但较弱,可以和一个名词连用,来表示某个或某些特定的人或东西. (1)特指双方都明白的人或物 Take the medicine.把药吃了. (2)上文提到过的人或事 He bought a house.他买了幢房子. I've been to the house.我去过那幢房子. (3)指世界上独一无二的事物 the sun ,the sky ,the moon, the earth (4)单数名词连用表示一类事物 the dollar 美元 the fox 狐狸 或与形容词或分词连用,表示一类人 the rich 富人 the living 生者 (5)用在序数词和形容词最高级,及形容词等前面 Where do you live?你住在哪? I live on the second floor.我住在二楼. That's the very thing I've been looking for.那正是我要找的东西. (6)与复数名词连用,指整个群体 They are the teachers of this school.(指全体教师) They are teachers of this school.(指部分教师) (7)表示所有,相当于物主代词,用在表示身体部位的名词前 She caught me by the arm.她抓住了我的手臂. (8)用在某些有普通名词构成的国家名称,机关团体,阶级等专有名词前 the People's Republic of China 中华人民共和国 the United States 美国 (9)用在表示乐器的名词前 She plays the piano.她会弹钢琴. (10)用在姓氏的复数名词之前,表示一家人 the Greens 格林一家人(或格林夫妇) (11)用在惯用语中 in the day, in the morning... the day before yesterday, the next morning... in the sky... in the dark... in the end... on the whole, by the way...

学生造句--Unit 1

●I wonder if it’s because I have been at school for so long that I’ve grown so crazy about going home. ●It is because she wasn’t well that she fell far behind her classmates this semester. ●I can well remember that there was a time when I took it for granted that friends should do everything for me. ●In order to make a difference to society, they spent almost all of their spare time in raising money for the charity. ●It’s no pleasure eating at school any longer because the food is not so tasty as that at home. ●He happened to be hit by a new idea when he was walking along the riverbank. ●I wonder if I can cope with stressful situations in life independently. ●It is because I take things for granted that I make so many mistakes. ●The treasure is so rare that a growing number of people are looking for it. ●He picks on the weak mn in order that we may pay attention to him. ●It’s no pleasure being disturbed whena I settle down to my work. ●I can well remember that when I was a child, I always made mistakes on purpose for fun. ●It’s no pleasure accompany her hanging out on the street on such a rainy day. ●I can well remember that there was a time when I threw my whole self into study in order to live up to my parents’ expectation and enter my dream university. ●I can well remember that she stuck with me all the time and helped me regain my confidence during my tough time five years ago. ●It is because he makes it a priority to study that he always gets good grades. ●I wonder if we should abandon this idea because there is no point in doing so. ●I wonder if it was because I ate ice-cream that I had an upset student this morning. ●It is because she refused to die that she became incredibly successful. ●She is so considerate that many of us turn to her for comfort. ●I can well remember that once I underestimated the power of words and hurt my friend. ●He works extremely hard in order to live up to his expectations. ●I happened to see a butterfly settle on the beautiful flower. ●It’s no pleasure making fun of others. ●It was the first time in the new semester that I had burned the midnight oil to study. ●It’s no pleasure taking everything into account when you long to have the relaxing life. ●I wonder if it was because he abandoned himself to despair that he was killed in a car accident when he was driving. ●Jack is always picking on younger children in order to show off his power. ●It is because he always burns the midnight oil that he oversleeps sometimes. ●I happened to find some pictures to do with my grandfather when I was going through the drawer. ●It was because I didn’t dare look at the failure face to face that I failed again. ●I tell my friend that failure is not scary in order that she can rebound from failure. ●I throw my whole self to study in order to pass the final exam. ●It was the first time that I had made a speech in public and enjoyed the thunder of applause. ●Alice happened to be on the street when a UFO landed right in front of her. ●It was the first time that I had kept myself open and talked sincerely with my parents. ●It was a beautiful sunny day. The weather was so comfortable that I settled myself into the

“the way+从句”结构的意义及用法

“tｈｅwａｙ+从句”结构的意义及用法 首先让我们来看下面这个句子: Ｒead the foｌloｗｉnｇpassagｅａnd talkａbout ｉt wi ｔh your classmaｔes．Try tｏｔeｌl whaｔyｏu thiｎk ｏf Tom aｎd ｏｆｔhe ｗay the chiｌｄrenｔrｅated ｈim. 在这个句子中，ｔhe waｙ是先行词,后面是省略了关系副词that或in whｉch的定语从句。 下面我们将叙述“the ｗaｙ+从句”结构的用法。 1.tｈe wａy之后，引导定语从句的关系词是tｈat而不是hoｗ,因此，<<现代英语惯用法词典＞＞中所给出的下面两个句子是错误的：Ｔhｉs is ｔｈeｗayｈowｉtｈａppened. This is the way how he ａlwａｙs treats me. 2．在正式语体中,thaｔ可被in which所代替;在非正式语体中，ｔhat则往往省略。由此我们得到theｗay后接定语从句时的三种模式：1) tｈe ｗaｙ＋ｔhａt-从句２）the way +ｉn whiｃh－从句3) the ｗay +从句 例如：Ｔｈe way(in whiｃh ，thａt) ｔhｅｓｅｃomｒade ｓloｏｋａｔｐrobｌems is wrong．这些同志看问题的方法

不对。 Ｔｈｅｗａy(that ,ｉn ｗhiｃh)yoｕ’ｒe doinｇit is comple ｔeｌy crａzy.你这么个干法,简直发疯。 Wｅａdmiｒｅd him for thｅｗay ｉｎｗhｉch he fａｃeｓdiｆficultieｓ． Waｌlａｃe ａｎd Ｄarwiｎｇreed ｏn the way ｉｎwhi ｃh ｄｉfｆｅrｅnt forms ｏf life had ｂegｕn.华莱士和达尔文对不同类型的生物是如何起源的持相同的观点。 Thｉs is ｔｈe ｗaｙ（tｈａｔ) hｅdｉd it. I lｉkeｄｔhe waｙ(ｔhat) ｓｈeｏｒganized ｔhe ｍeetｉng． 3.theｗay(tｈat)有时可以与hｏw(作“如何”解）通用。例如： That’s tｈe ｗaｙ(tｈaｔ) shｅspoke. = Tｈat’s how shｅspoke.

知己的近义词反义词及知己的造句

知己的近义词反义词及知己的造句 本文是关于知己的近义词反义词及知己的造句，感谢您的阅读！ 知己的近义词反义词及知己的造句知己 基本解释：顾名思义是了解、理解、赏识自己的人，如"知己知彼，百战不殆";更常指懂你自己的挚友或密友，它是一生难求的朋友，友情的最高境界。正所谓:"士为知己者死"。 1.谓了解、理解、赏识、懂自己。 2.彼此相知而情谊深切的人。 【知己近义词】 亲信，好友，密友，心腹，挚友，深交，相知，知交，知友，知心，知音，石友，老友，至友 【知己反义词】 仇人敌人陌路 【知己造句】 1、我们想要被人爱、想拥有知己、想历经欢乐、想要安全感。 2、朋友本应是我们的亲密知己和支持者，但对于大多数人来说，有一些朋友比起帮助我们，更多的却是阻碍。 3、那么，为什么你就认为，随着年龄的增长，比起女人来男人们的知己和丰富的人际关系更少，因此一般容易更孤独呢？ 4、他成了我的朋友、我的知己、我的顾问。 5、无论在我当州长还是总统的时候，布鲁斯都是我的密友、顾问和知己。他这样的朋友人人需要，也是所有总统必须拥有的。

6、波兰斯基有着一段声名卓著的电影生涯，也是几乎所有电影界重要人物们的挚友和同事，他们是知己，是亲密的伙伴。 7、搜索引擎变成了可以帮追我们的忏悔室，知己，信得过的朋友。 8、这样看来，奥巴马国家安全团队中最具影响力的当属盖茨了――但他却是共和党人，他不会就五角大楼以外问题发表看法或成为总统知己。 9、我们的关系在二十年前就已经和平的结束了，但在网上，我又一次成为了他精神层面上的评论家，拉拉队，以及红颜知己。 10、这位“知己”，作为拍摄者，站在距离电视屏幕几英尺的地方对比着自己年轻版的形象。 11、父亲与儿子相互被形容为对方的政治扩音筒、知己和后援。 12、这对夫妻几乎没有什么至交或知己依然在世，而他们在后纳粹时期的德国也不可能会说出实话的。 13、她把我当作知己，于是，我便将她和情人之间的争吵了解得一清二楚。 14、有一种友谊不低于爱情；关系不属于暖昧；倾诉一直推心置腹；结局总是难成眷属；这就是知己！ 15、把你的治疗师当做是可以分享一切心事的知己。 16、莉莉安对我敞开心胸，我成了她的知己。 17、据盖洛普民意调查显示，在那些自我认同的保守党人中，尽管布什仍维持72%支持率，但他在共和党领导层中似乎很少有几位知

英语句子结构和造句

高中英语~词性~句子成分~语法构成 第一章节：英语句子中的词性 1.名词：n. 名词是指事物的名称，在句子中主要作主语.宾语.表语.同位语。 2.形容词;adj. 形容词是指对名词进行修饰~限定~描述~的成份，主要作定语.表语.。形容词在汉语中是（的）.其标志是: ous. Al .ful .ive。. 3.动词：vt. 动词是指主语发出的一个动作，一般用来作谓语。 4.副词：adv. 副词是指表示动作发生的地点. 时间. 条件. 方式. 原因. 目的. 结果.伴随让步. 一般用来修饰动词. 形容词。副词在汉语中是（地）.其标志是：ly。 5.代词：pron. 代词是指用来代替名词的词，名词所能担任的作用，代词也同样.代词主要用来作主语. 宾语. 表语. 同位语。 6.介词：prep.介词是指表示动词和名次关系的词，例如：in on at of about with for to。其特征：

介词后的动词要用—ing形式。介词加代词时，代词要用宾格。例如：give up her（him）这种形式是正确的，而give up she（he）这种形式是错误的。 7.冠词：冠词是指修饰名词，表名词泛指或特指。冠词有a an the 。 8.叹词：叹词表示一种语气。例如：OH. Ya 等 9.连词：连词是指连接两个并列的成分，这两个并列的成分可以是两个词也可以是两个句子。例如：and but or so 。 10.数词：数词是指表示数量关系词，一般分为基数词和序数词 第二章节：英语句子成分 主语：动作的发出者，一般放在动词前或句首。由名词. 代词. 数词. 不定时. 动名词. 或从句充当。 谓语：指主语发出来的动作，只能由动词充当，一般紧跟在主语后面。 宾语：指动作的承受着，一般由代词. 名词. 数词. 不定时. 动名词. 或从句充当. 介词后面的成分也叫介词宾语。 定语：只对名词起限定修饰的成分，一般由形容

way 用法

表示“方式”、“方法”，注意以下用法： 1.表示用某种方法或按某种方式，通常用介词in(此介词有时可省略)。如： Do it (in) your own way. 按你自己的方法做吧。 Please do not talk (in) that way. 请不要那样说。 2.表示做某事的方式或方法，其后可接不定式或of doing sth。 如： It’s the best way of studying [to study] English. 这是学习英语的最好方法。 There are different ways to do [of doing] it. 做这事有不同的办法。 3.其后通常可直接跟一个定语从句(不用任何引导词)，也可跟由that 或in which 引导的定语从句，但是其后的从句不能由how 来引导。如： 我不喜欢他说话的态度。 正：I don’t like the way he spoke. 正：I don’t like the way that he spoke. 正：I don’t like the way in which he spoke. 误：I don’t like the way how he spoke. 4.注意以下各句the way 的用法： That’s the way (=how) he spoke. 那就是他说话的方式。 Nobody else loves you the way(=as) I do. 没有人像我这样爱你。 The way (=According as) you are studying now, you won’tmake much progress. 根据你现在学习情况来看，你不会有多大的进步。 2007年陕西省高考英语中有这样一道单项填空题： ——I think he is taking an active part insocial work. ——I agree with you_____. A、in a way B、on the way C、by the way D、in the way 此题答案选A。要想弄清为什么选A，而不选其他几项，则要弄清选项中含way的四个短语的不同意义和用法，下面我们就对此作一归纳和小结。 一、in a way的用法 表示：在一定程度上，从某方面说。如： In a way he was right.在某种程度上他是对的。注：in a way也可说成in one way。 二、on the way的用法 1、表示：即将来(去)，就要来(去)。如： Spring is on the way.春天快到了。 I'd better be on my way soon.我最好还是快点儿走。 Radio forecasts said a sixth-grade wind was on the way.无线电预报说将有六级大风。 2、表示：在路上，在行进中。如： He stopped for breakfast on the way.他中途停下吃早点。 We had some good laughs on the way.我们在路上好好笑了一阵子。 3、表示：(婴儿)尚未出生。如： She has two children with another one on the way.她有两个孩子，现在还怀着一个。 She's got five children，and another one is on the way.她已经有5个孩子了，另一个又快生了。 三、by the way的用法

六级单词解析造句记忆MNO

M A: Has the case been closed yet? B: No, the magistrate still needs to decide the outcome. magistrate n.地方行政官，地方法官，治安官 A: I am unable to read the small print in the book. B: It seems you need to magnify it. magnify vt.１．放大，扩大；２．夸大，夸张 A: That was a terrible storm. B: Indeed, but it is too early to determine the magnitude of the damage. magnitude n.１．重要性，重大；２．巨大，广大 A: A young fair maiden like you shouldn’t be single. B: That is because I am a young fair independent maiden. maiden n.少女，年轻姑娘，未婚女子 a.首次的，初次的 A: You look majestic sitting on that high chair. B: Yes, I am pretending to be the king! majestic a.雄伟的，壮丽的，庄严的，高贵的 A: Please cook me dinner now. B: Yes, your majesty, I’m at your service. majesty n.１．［Ｍ－］陛下（对帝王，王后的尊称）；２．雄伟，壮丽，庄严 A: Doctor, I traveled to Africa and I think I caught malaria. B: Did you take any medicine as a precaution? malaria n.疟疾 A: I hate you! B: Why are you so full of malice? malice n.恶意，怨恨 A: I’m afraid that the test results have come back and your lump is malignant. B: That means it’s serious, doesn’t it, doctor? malignant a.１．恶性的，致命的；２．恶意的，恶毒的 A: I’m going shopping in the mall this afternoon, want to join me? B: No, thanks, I have plans already. mall n.（由许多商店组成的）购物中心 A: That child looks very unhealthy. B: Yes, he does not have enough to eat. He is suffering from malnutrition.

小学语文反义词仿照的近义词反义词和造句

仿照的近义词反义词和造句 仿照的近义词 【仿制解释】：仿造：～品 【模仿解释】：个体自觉或不自觉地重复他人的行为的过程。是社会学习的重要形式之一。尤其在儿童方面，儿童的动作、语言、技能以及行为习惯、品质等的形成和发展都离不开模仿。可分为无意识模仿和有意识模仿、外部模仿和内部模仿等多种类型。 仿照的反义词 【独创解释】：独特的创造：～精神ㄧ～一格。 仿照造句 一、老师让我们仿照黑板上的图画一幅画。 二、仿照下面的句式，以“只有”开头，写一结构与之相似的复句。 三、仿照例句的句子，在下面两句的横线上补写相应的内容。 四、仿照例句，以“记忆”或“友情”开头，另写一句话。 五、仿照下面两个例句，用恰当的词语完成句子，要求前后语意关联。 六、仿照开头两句句式，通过联想，在后面两句横线上填上相应的词语。 七、仿照所给例句，用下面的词展开联想，给它一个精彩的解释。 八、仿照例句，以“你”开头，另写一个句子。 九、仿照下列句式，续写两个句子，使之与前文组成意义相关的.句子。 十、我们也仿照八股文章的笔法来一个“八股”,以毒攻毒,就叫做八大罪状吧。

十一、仿照例句，任选一种事物，写一个句子。 十二、仿照下面一句话的句式和修辞，以“时间”开头，接着写一个句子。 十三、仿照例句，以“热爱”开头，另写一句子。 十四、仿照下面的比喻形式，另写一组句子。要求选择新的本体和喻体，意思完整。 十五、根据语镜，仿照划线句子，接写两句，构成语意连贯的一段话。 十六、仿照下面句式，续写两个句式相同的比喻句。 十七、自选话题，仿照下面句子的形式和修辞，写一组排比句。 十八、仿照下面一句话的句式，仍以“人生”开头，接着写一句话。 十九、仿照例句的格式和修辞特点续写两个句子，使之与例句构成一组排比句。 二十、仿照例句，另写一个句子，要求能恰当地表达自己的愿望。 二十一、仿照下面一句话的句式，接着写一句话，使之与前面的内容、句式相对应，修辞方法相同。 二十二、仿照下面一句话的句式和修辞，以“思考”开头，接着写一个句子。 二十三、仿照下面例句，从ABCD四个英文字母中选取一个，以”青春”为话题，展开想象和联想，写一段运用了比喻修辞格、意蕴丰富的话，要求不少于30字。 二十四、仿照下面例句，另写一个句子。 二十五、仿照例句，另写一个句子。 二十六、下面是毕业前夕的班会上，数学老师为同学们写的一句赠言，请你仿照它的特点，以语文老师的身份为同学们也写一句。

base on的例句

意见应以事实为根据. 3 来自辞典例句 192. The bombers swooped ( down ) onthe air base. 轰炸机 突袭 空军基地. 来自辞典例句 193. He mounted their engines on a rubber base. 他把他们的发动机装在一个橡胶垫座上. 14 来自辞典例句 194. The column stands on a narrow base. 柱子竖立在狭窄的地基上. 14 来自辞典例句 195. When one stretched it, it looked like grey flakes on the carvas base. 你要是把它摊直, 看上去就象好一些灰色的粉片落在帆布底子上. 18 来自辞典例句 196. Economic growth and human well - being depend on the natural resource base that supports all living systems. 经济增长和人类的福利依赖于支持所有生命系统的自然资源. 12 1 来自辞典例句 197. The base was just a smudge onthe untouched hundred - mile coast of Manila Bay. 那基地只是马尼拉湾一百英里长安然无恙的海岸线上一个硝烟滚滚的污点. 6 来自辞典例句 198. You can't base an operation on the presumption that miracles are going to happen. 你不能把行动计划建筑在可能出现奇迹的假想基础上.

The way的用法及其含义(一)

The way的用法及其含义（一） 有这样一个句子：In 1770 the room was completed the way she wanted. 1770年，这间琥珀屋按照她的要求完成了。 the way在句中的语法作用是什么？其意义如何？在阅读时，学生经常会碰到一些含有the way 的句子，如：No one knows the way he invented the machine. He did not do the experiment the way his teacher told him.等等。他们对the way 的用法和含义比较模糊。在这几个句子中，the way之后的部分都是定语从句。第一句的意思是，“没人知道他是怎样发明这台机器的。”the way的意思相当于how；第二句的意思是，“他没有按照老师说的那样做实验。”the way 的意思相当于as。在In 1770 the room was completed the way she wanted.这句话中，the way也是as的含义。随着现代英语的发展，the way的用法已越来越普遍了。下面，我们从the way的语法作用和意义等方面做一考查和分析： 一、the way作先行词，后接定语从句 以下3种表达都是正确的。例如：“我喜欢她笑的样子。” 1. the way+ in which +从句 I like the way in which she smiles. 2. the way+ that +从句 I like the way that she smiles. 3. the way + 从句(省略了in which或that) I like the way she smiles. 又如：“火灾如何发生的，有好几种说法。” 1. There were several theories about the way in which the fire started. 2. There were several theories about the way that the fire started.