Partitioning arrangements of lines I: An efficient deterministic algorithm

In this paper we consider the following problem: Given a set ofn lines in the plane, partition the plane intoO(r ²) triangles so that no triangle meets more thanO(n/r) lines of . We present a deterministic algorithm for this problem withO(nr logn/r) running time, where is a constant <3.33.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th Annual Symposium on Computational Geometry, 1989, pp. 11–22.     

Storing line segments in partition trees

We design two variants of partition trees, calledsegment partition trees andinterval partition trees, that can be used for storing arbitrarily oriented line segments in the plane in an efficient way. The raw structures useO(n logn) andO(n) storage, respectively, and their construction time isO(n logn). In our applications we augment these structures by certain (simple) auxiliary structures, which may increase the storage and preprocessing time by a polylogarithmic factor. It is shown how to use these structures for solving line segment intersection queries, triangle stabbing queries and ray shooting queries in reasonably efficient ways. If we use the conjugation tree as the underlying partition tree, the query time for all problems isO(n ), where=log₂(1+5)–10.695. The techniques are fairly simple and easy to understand.Research of the first author was partially supported by the ESPRIT II Basic Research Action of the EC under contract No. 3075 (Project ALCOM).Work by the third author has been supported in part by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the Digital Equipment Corporation, the IBM Corporation, the U.S.-Israeli Binational Science Foundation, the NCRD — the Israeli National Council for Research and Development, and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.     

Partitioning arrangements of lines II: Applications

In this paper we present efficient deterministic algorithms for various problems involving lines or segments in the plane, using the partitioning algorithm described in a companion paper [A3]. These applications include: (i) anO(m ^2/3 n ^2/3 · log^2/3 n · log^/3 (m/n)+(m+n) logn) algorithm to compute all incidences betweenm points andn lines, where is a constant <3.33; (ii) anO(m ^2/3 n ^2/3 · log^5/3 n · log^/3 (m/n)+(m+n) logn) algorithm to computem faces in an arrangement ofn lines; (iii) anO(n ^4/3 log^(+2)/3 n) algorithm to count the number of intersections in a set ofn segments; (iv) anO(n ^4/3 log^{( + 2)/3} n) algorithm to count red-blue intersections between two sets of segments, and (v) anO(n ^3/2 log^/3 n) algorithm to compute spanning trees with low stabbing number for a set ofn points. We also present an algorithm that, given set ofn points in the plane, preprocesses it, in timeO(nm log^+1/2 n), into a data structure of sizeO(m) forn lognmn ², so that the number of points ofS lying inside a query triangle can be computed inO((n/m) log^3/2 n) time.Work on this paper has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. A preliminary version of this paper appears in theProceedings of the 5th ACM Symposium on Computational Geometry, 1989, pp. 11–22.     

On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space

We show that the number of critical positions of a convex polygonal objectB moving amidst polygonal barriers in two-dimensional space, at which it makes three simultaneous contacts with the obstacles but does not penetrate into any obstacle isO(kn _s (kn)) for somes6, wherek is the number of boundary segments ofB,n is the number of wall segments, and _s (q) is an almost linear function ofq yielding the maximal number of breakpoints along the lower envelope (i.e., pointwise minimum) of a set ofq continuous functions each pair of which intersect in at mosts points (here a breakpoint is a point at which two of the functions simultaneously attain the minimum). We also present an example where the number of such critical contacts is (k ² n ²), showing that in the worst case our upper bound is almost optimal.Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

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

We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m ^2/3– n ^2/3+2 +n) for any>0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m ^2/3– n ^2/3+2 logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m ^2/3– n ^2/3+2 +n (n) logm) for any>0, where(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m ^2/3– n ^2/3+2 log+n(n) log² n logm).The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation under Grant CCR-8714565. Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD-the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.     

Lower bounds on moving a ladder in two and three dimensions

It is shown that (n ²) distinct moves may be necessary to move a line segment (a ladder) in the plane from an initial to a final position in the presence of polygonal obstacles of a total ofn vertices, and that (n ⁴) moves may be necessary for the same problem in three dimensions. These two results establish lower bounds on algorithms that solve the motion-planning problems by listing the moves of the ladder. The best upper bounds known areO(n ² logn) in two dimensions, andO(n ⁵ logn) in three dimensions.This work was partially supported by NSF Grants DCR-83-51468 and grants from Martin Marietta, IBM, and General Motors.     

Improved lower bounds on the length of Davenport-Schinzel sequences

We derive lower bounds on the maximal length _s(n) of (n, s) Davenport Schinzel sequences. These bounds have the form _2s=1(n)=(n^s(n)), where(n) is the extremely slowly growing functional inverse of the Ackermann function. These bounds extend the nonlinear lower bound ₃ (n)=(n(n)) due to Hart and Sharir [5], and are obtained by an inductive construction based upon the construction given in [5].Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.     

Error estimates for the finite element solution of variational inequalities

Summary We analyze the convergence of finite element approximations of some variational inequalities namely the obstacle problem and the unilateral problem. OptimalO(h) andO(h^3/2–) error bounds for the obstacle problem (for linear and quadratic elements) and anO(h) error bound for the unilateral problem (with linear elements) are proved.Supported in part by the Institut de Recherche d'Informatique et d'Automatique and by National Science Foundation grant MCS 75-09457     

The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis

Letf ₁, ...,f _m be (partially defined) piecewise linear functions ofd variables whose graphs consist ofn d-simplices altogether. We show that the maximal number ofd-faces comprising the upper envelope (i.e., the pointwise maximum) of these functions isO(n ^d (n)), where(n) denotes the inverse of the Ackermann function, and that this bound is tight in the worst case. If, instead of the upper envelope, we consider any single connected componentC enclosed byn d-simplices (or, more generally, (d – 1)-dimensional compact convex sets) in ^d+1 , then we show that the overall combinatorial complexity of the boundary ofC is at mostO(n ^d+1–(d+1) ) for some fixed constant(d+1)>0.Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development.     

On the zone of a surface in a hyperplane arrangement

LetH be a collection ofn hyperplanes in ^d , letA denote the arrangement ofH, and let be a (d–1)-dimensional algebraic surface of low degree, or the boundary of a convex set in ^d . Thezone of inA is the collection of cells ofA crossed by . We show that the total number of faces bounding the cells of the zone of isO(n ^d–1 logn). More generally, if has dimensionp, 0p<d, this quantity isO(n ^[(d+p)/2]) ford–p even andO(n ^[(d+p)/2] logn) ford–p odd. These bounds are tight within a logarithmic factor.This paper is the union of two conference proceedings papers [3], [15]. Work on this paper by M. Pellegrini and M. Sharir has been supported by NSF Grant CCR-8901484. Work on this paper by M. Sharir has also been supported by ONR Grant N00014-90-J-1284 and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F. (the German-Israeli Foundation for Scientific Research and Development), and the Fund for Basic Research administered by the Israeli Academy of Sciences. M. Pellegrini's current address is Department of Computing, King's College, Strand, London WC2R 2LS, England.     

Orthogonal rational functions and quadrature on the unit circle

In this paper we shall be concerned with the problem of approximating the integralI {f}= _– f(eⁱ) d(), by means of the formulaI _n {f}= _j=1 ⁿ A _j ⁽ⁿ⁾ f(x _j ⁽ⁿ⁾ ) where is some finite positive measure. We want the approximation to be so thatI _n{f}=I {f} forf belonging to certain classes of rational functions with prescribed poles which generalize in a certain sense the space of polynomials. In order to get nodes {x _j ⁽ⁿ⁾ } of modulus 1 and positive weightsA _j ⁽ⁿ⁾ , it will be fundamental to use rational functions orthogonal on the unit circle analogous to Szeg polynomials.The work of the first author is partially supported by a research grant from the Belgian National Fund for Scientific Research.     

On asymptotics of solutions to semilinear elliptic equations near the first eigenvalue of the nonperturbed problem

We writef=(g) iff(x)cg(x) with some positive constantc for allx from the domain of functionsf andg. We show that at least (n ² /r) entries must be changed in an arbitrary (generalized) Hadamard matrix in order to reduce its rank belowr. This improves the previously known bound (n ²/r ²). If we additionally know that the changes are bounded above in absolute value by some numbern/r, then the number of these entries is bounded below by (n ³/(r ² )), which improves upon the previously known bound (n ² / ² ).Translated fromMatematicheskie Zametki, Vol. 63, No. 4, pp. 535–540, April, 1998.The research of the first author was supported by the Russian Foundation for Basic Research under grants No. 96-01-00094 and No. 96-15-96102 and by the INTAS Foundation under grant No. 93-1376. The research of the second author was supported by the Russian Foundation for Basic Research under grants No. 96-01-01222 and No. 96-15-96090.     

Separating two simple polygons by a sequence of translations

LetP andQ be two disjoint simple polygons havingm andn sides, respectively. We present an algorithm which determines whetherQ can be moved by a sequence of translations to a position sufficiently far fromP without colliding withP, and which produces such a motion if it exists. Our algorithm runs in timeO(mn(mn) logm logn) where (k) is the extremely slowly growing inverse Ackermann's function. Since in the worst case (mn) translations may be necessary to separateQ fromP, our algorithm is close to optimal.Work on this paper by the first author has been supported by National Science Foundation Grant No. DMS-8501947. Work on this paper by the second author has been supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSP-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the second and third authors has also been supported by a grant from the joint Ramot-Israeli Ministry of Industry Foundation. Part of the work on this paper has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986.     

Outer approximation algorithm for nondifferentiable optimization problems

It is known that the problem of minimizing a convex functionf(x) over a compact subsetX of ⁿ can be expressed as minimizing max{g(x, y)|y X}, whereg is a support function forf[f(x) g(x, y), for ally X andf(x)=g(x, x)]. Standard outer-approximation theory can then be employed to obtain outer-approximation algorithms with procedures for dropping previous cuts. It is shown here how this methodology can be extended to nonconvex nondifferentiable functions.This research was supported by the Science and Engineering Research Council, UK, and by the National Science Foundation under Grant No. ECS-79-13148.     

Generic properties of the complementarity problem

Givenf: R ₊ ⁿ R ⁿ , the complementarity problem is to find a solution tox 0,f(x) 0, and x, f(x) = 0. Under the condition thatf is continuously differentiable, we prove that for a generic set of such anf, the problem has a discrete solution set. Also, under a set of generic nondegeneracy conditions and a condition that implies existence, we prove that the problem has an odd number of solutions.This work was partially supported by N.S.F. Grants GP-8007 and 010185.     

Implicitly representing arrangements of lines or segments

Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n ²) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with (n) space¹ and (n ^3/2) preprocessing time, we can answer face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, (2) given a simple polygonal path , form a data structure from which we can find the convex hull of any subpath of quickly, and (3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in (n ^1/3)+O(K) time, given(n ^4/3) space and (n ^5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time (m ^2/3 n ^2/3+n), which is nearly optimal.The first author is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565. Work on this paper by the fifth author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. The sixth author was supported in part by a National Science Foundation Graduate Fellowship. This work was begun while the non-DEC authors were visiting at the DEC Systems Research Center.     

Improvement on the northby algorithm for molecular conformation: Better solutions

In 1987, Northby presented an efficient lattice based search and optimization procedure to compute ground states ofn-atom Lennard-Jones clusters and reported putative global minima for 13n150. In this paper, we introduce simple data structures which reduce the time complexity of the Northby algorithm for lattice search fromO(n^5/3) per move toO(n^2/3) per move for ann-atom cluster involving full Lennard-Jones potential function. If nearest neighbor potential function is used, the time complexity can be further reduced toO(logn) per move for ann-atom cluster. The lattice local minimizers with lowest potential function values are relaxed by a powerful Truncated Newton algorithm. We are able to reproduce the minima reported by Northby. The improved algorithm is so efficient that less than 3 minutes of CPU time on the Cray-XMP is required for each cluster size in the above range. We then further improve the Northby algorithm by relaxingevery lattice local minimizer found in the process. This certainly requires more time. However, lower energy configurations were found with this improved algorithm forn=65, 66, 75, 76, 77 and 134. These findings also show that in some cases, the relaxation of a lattice local minimizer with a worse potential function value may lead to a local minimizer with a better potential function value.     

Random Walks Crossing High Level Curved Boundaries

Let {S _n} be a random walk, generated by i.i.d. increments X _i which drifts weakly to in the sense that as n . Suppose k0, k1, and E|X ₁|^1\k = if k>1. Then we show that the probability that S. crosses the curve nan ^K before it crosses the curve n –an ^k tends to 1 as a . This intuitively plausible result is not true for k = 1, however, and for 1/2 <k<1, the converse results are not true in general, either. More general boundaries g(n) than g(n) = n ^k are also considered, and we also prove similar results for first passages out of regions like { (n, y): n1, |y| (a + n) ^k } as a .     

Approximating the ball by a minkowski sum of segments with equal length

It is proved that forn 2 the Euclidean ballB _n can be approximated up to (in the Hausdorff distance) by a zonotope havingN summands of equal length withN c(n)( ^–2|log|)^{(n–1)/(n+2)}.Research supported in part by the U.S.-Israeli Binational Science Foundation. [Please see the Editors' note on the first page of the preceding paper.]     

An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space

We present an efficient algorithm for planning the motion of a convex polygonal bodyB in two-dimensional space bounded by a collection of polygonal obstacles. Our algorithm extends and combines the techniques of Leven and Sharir and of Sifrony and Sharir used for the case in whichB is a line segment (a ladder). It also makes use of the results of Kedem and Sharir on the planning of translational motion ofB amidst polygonal obstacles, and of a recent result of Leven and Sharir on the number of free critical contacts ofB with such polygonal obstacles. The algorithm runs in timeO(kn ₆(kn) logkn), wherek is the number of sides ofB, n is the number of obstacle edges, and ,(q) is an almost linear function ofq yielding the maximal number of connected portions ofq continuous functions which compose the graph of their lower envelope, where it is assumed that each pair of these functions intersect in at mosts points.Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.