Upper bounds for configurations and polytopes inR d

We give a new upper bound onn ^d(d+1)n on the number of realizable order types of simple configurations ofn points inR ^d , and ofn2d ² n on the number of realizable combinatorial types of simple configurations. It follows as a corollary of the first result that there are no more thann ^d(d+1)n combinatorially distinct labeled simplicial polytopes inR ^d withn vertices, which improves the best previous upper bound ofn ^{cn d/2}.Supported in part by NSF Grant DMS-8501492 and PSC-CUNY Grant 665258.Supported in part by NSF Grant DMS-8501947.     

Counting facets and incidences

We show thatm distinct cells in an arrangement ofn planes in ³ are bounded byO(m ^2/3 n+n ²) faces, which in turn yields a tight bound on the maximum number of facets boundingm cells in an arrangement ofn hyperplanes in ^d , for everyd3. In addition, the method is extended to obtain tight bounds on the maximum number of faces on the boundary of all nonconvex cells in an arrangement of triangles in ³. We also present a simpler proof of theO(m ^2/3 n ^d/3+n ^d–1) bound on the number of incidences betweenn hyperplanes in ^d andm vertices of their arrangement.Work on this paper was supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center Grant NSF-STC88-09648, and by NSA Grant MDA 904-89-H-2030.     

A matroid algorithm and its application to the efficient solution of two optimization problems on graphs

We address the problem of finding a minimum weight baseB of a matroid when, in addition, each element of the matroid is colored with one ofm colors and there are upper and lower bound restrictions on the number of elements ofB with colori, fori = 1, 2,,m. This problem is a special case of matroid intersection. We present an algorithm that exploits the special structure, and we apply it to two optimization problems on graphs. When applied to the weighted bipartite matching problem, our algorithm has complexity O(|EV|+|V| ²log|V|). HereV denotes the node set of the underlying bipartite graph, andE denotes its edge set. The second application is defined on a general connected graphG = (V,E) whose edges have a weight and a color. One seeks a minimum weight spanning tree with upper and lower bound restrictions on the number of edges with colori in the tree, for eachi. Our algorithm for this problem has complexity O(|EV|+m ² |V|+ m|V| ²). A special case of this constrained spanning tree problem occurs whenV ^* is a set of pairwise nonadjacent nodes ofG. One must find a minimum weight spanning tree with upper and lower bound restrictions on the degree of each node ofV ^*. Then the complexity of our algorithm is O(|VE|+|V ^* V| ²). Finally, we discuss a new relaxation of the traveling salesman problem.This report was supported in part by NSF grant ECS 8601660.     

Limit of Solutions of a SDE with a Large Drift Driven by a Poisson Random Measure

We consider a sequence of {X _n} of R ^d-valued processes satisfying a stochastic differential equation driven by a Brownian motion and a compensated Poisson random measure, with _n ~ _n with a large drift. Let be a m-dimensional submanifold (m<d), where F vanishes. Then under some suitable growth conditions for _n ~ _n, and some conditions for F, we show that dist(X _n, )0 before it exits any given compact set, that is, the large drift term forces X _n close to . And if the coefficients converge to some continuous functions, any limit process must actually stay on and satisfy a certain stochastic differential equation driven by Brownian motion and white noise.     

The upper envelope of voronoi surfaces and its applications

Given a setS ofsources (points or segments) in 211C;^d, we consider the surface in 211C; ^d+1 that is the graph of the functiond(x)=min _pS (x, p) for some metric. This surface is closely related to the Voronoi diagram, Vor(S), ofS under the metric. The upper envelope of a set of theseVoronoi surfaces, each defined for a different set of sources, can be used to solve the problem of finding the minimum Hausdorff distance between two sets of points or line segments under translation. We derive bounds on the number of vertices on the upper envelope of a collection of Voronoi surfaces, and provide efficient algorithms to calculate these vertices. We then discuss applications of the methods to the problems of finding the minimum Hausdorff distance under translation, between sets of points and segments.The first author was supported in part by NSF PYI Grant IRI-9057928 and matching funds from General Electric, Kodak, and Xerox, and by U.S. Air Force Contract AFOSR-91-0328. The second and third authors were supported by the Fund for Basic Research administered by the Israeli Academy of Sciences. The second author was also supported by a fellowship from the Pikkowski-Valazzi Fund and by the Eshkol Grant 04601-90 from the Israeli Ministry of Science and Technology. The third author was also supported by Office of Naval Research Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, by grants from the U.S.-Israeli Binational Science Foundation, from the Basic Research Fund administered by the Israeli Academy of Sciences, and from G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Independent collections of translates of boxes and a conjecture due to Grünbaum

A collection ofn setsA ₁, ...,A _n is said to beindependent provided every set of the formX ₁ ... X _n is nonempty, where eachX _i is eitherA _i orA _i ^c . We give a simple characterization for when translates of a given box form an independent set inR ^d. We use this to show that the largest number of such boxes forming an independent set inR ^d is given by 3d/2 ford2. This settles in the negative a conjecture of Grünbaum (1975), which states that the maximum size of an independent collection of sets homothetic to a fixed convex setC inR ^d isd+1. It also shows that the bound of 2d of Rényiet al. (1951) for the maximum number of boxes (not necessarily translates of a given one) with sides parallel to the coordinate axes in an independent collection inR ^d can be improved for these special collections.Daniel Q. Naiman was supported by National Science Foundation Grant No. DMS-9103126. Henry P. Wynn was supported by the Science and Engineering Research Council, UK.     

On the strong law of large numbers for dependent random variables

Let {X _n} _n ^=1/∞ be a sequence of random variables with partial sumsS _n, and let {ie241-1} be the σ-algebra generated byX ₁,…,X _n. Letf be a function fromR toR and suppose {ie241-2}. Under conditions off and moment conditions on theX' _ns, we show thatS _n/n converges a.e. (almost everywhere). We give several applications of this result. Research supported by N.S.F. Grant MCS 77-26809     

A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra

We present a new pivot-based algorithm which can be used with minor modification for the enumeration of the facets of the convex hull of a set of points, or for the enumeration of the vertices of an arrangement or of a convex polyhedron, in arbitrary dimension. The algorithm has the following properties:

The Steiner ratio conjecture for cocircular points

A Steiner minimal treeS is a network of shortest possible length connecting a set ofn points in the plane. LetT be a shortest tree connecting then points but with vertices only at these points.T is called a minimal spanning tree. The Steiner ratio conjecture is that the length ofS divided by the length ofT is at least 3/2. In this paper we use a variational approach to show that if then points lie on a circle, then the Steiner ratio conjecture holds.     

Points and triangles in the plane and halving planes in space

We prove that for any setS ofn points in the plane andn ^3−α triangles spanned by the points inS there exists a point (not necessarily inS) contained in at leastn ^3−3α/(c log⁵ n) of the triangles. This implies that any set ofn points in three-dimensional space defines at most halving planes. Work on this paper by Boris Aronov and Rephael Wenger has been supported by DIMACS under NSF Grant STC-88-09648. Work on this paper by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-87-14565. Micha Sharir has been supported by ONR Grant N00014-87-K-0129, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Israeli National Council for Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Cycles through specified vertices

Recently, various authors have obtained results about the existence of long cycles in graphs with a given minimum degreed. We extend these results to the case where only some of the vertices are known to have degree at leastd, and we want to find a cycle through as many of these vertices as possible. IfG is a graph onn vertices andW is a set ofw vertices of degree at leastd, we prove that there is a cycle through at least vertices ofW. We also find the extremal graphs for this property.Research supported in part by NSF Grant DMS 8806097     

Efficient robust estimates in parametric models

Summary Let {P ⁿ :}, an open subset ofR ^k , be a regular parametric model for a sample ofn independent, identically distributed observations. This paper describes estimates {T _n ;n1} of which are asymptotically efficient under the parametric model and are robust under small deviations from that model. In essence, the estimates are adaptively modified, one-step maximum likelihood estimates, which adjust themselves according to how well the parametric model appears to fit the data. When the fit seems poor,T _n discounts observations that would have large influence on the value of the usual one-step MLE. The estimates {T _n } are shown to be asymptotically minimax, in the Hájek-LeCam sense, for a Hellinger ball contamination model. An alternative construction of robust asymptotically minimax estimates, as modified MLE's, is described for canonical exponential families.This research was supported in part by National Science Foundation Grant MCS 75-10376     

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.     

Can you cover your shadows?

A subsetX of thed-dimensional Euclidean space ^d can cover its shadows inR ^d , if every orthogonal projection ofX onto a (d–1)-dimensional linear subspace of ^d is contained in some congruent copy ofX. Whereas every two-dimensional convex discC R ^d has this property, no (d–1)-polytope does, provided thatd>-4.     

Improved bounds on weak ε-nets for convex sets

LetS be a set ofn points in ℝ ^d . A setW is aweak ε-net for (convex ranges of)S if, for anyT⊆S containing εn points, the convex hull ofT intersectsW. We show the existence of weak ε-nets of size , whereβ ₂=0,β ₃=1, andβ _d ≈0.149·2 ^d-1(d-1)!, improving a previous bound of Alonet al. Such a net can be computed effectively. We also consider two special cases: whenS is a planar point set in convex position, we prove the existence of a net of sizeO((1/ε) log^1.6(1/ε)). In the case whereS consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of sizeO(1/ε), which improves a previous bound of Capoyleas. Work by Bernard Chazelle has been supported by NSF Grant CCR-90-02352 and the Geometry Center. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-89-21421. Work by Michelangelo Grigni has been supported by NSERC Operating Grants and NSF Grant DMS-9206251. Work by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Emo Welzl and Micha Sharir has been supported by a grant from the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Work by Micha Sharir has also been supported by NSF Grant CCR-91-22103, and by a grant from the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Leafy spanning trees in hypercubes

We prove that the d-dimensional hypercube, Q_d, with n = 2^d vertices, contains a spanning tree with at least

leaves. This improves upon the bound implied by a more general result on spanning trees in graphs with minimum degree δ, which gives (1 − O(log log n)/log₂n)n as a lower bound on the maximum number of leaves in spanning trees of n-vertex hypercubes.     

The asymptotic behavior of the principal eigenvalue in a singular perturbation problem with invariant boundaries

Summary We consider diffusion random perturbations of a dynamical systemS ^t in a domainGR ^m which, in particular, may be invariant under the action ofS ^t. Continuing the study of [K1-K4] we find the asymptotic behavior of the principal eigenvalue of the corresponding generator when the diffusion term tends to zero.This work was supported by U.S.A.-Israel B.S.F. Grant #84-00028     

On the computation of multi-dimensional solution manifolds of parametrized equations

Summary A new algorithm is presented for computing vertices of a simplicial triangulation of thep-dimensional solution manifold of a parametrized equationF(x)=0, whereF is a nonlinear mapping fromR ⁿ toR ^m ,p=n–m>1. An essential part of the method is a constructive algorithm for computing moving frames on the manifold; that is, of orthonormal bases of the tangent spaces that vary smoothly with their points of contact. The triangulation algorithm uses these bases, together with a chord form of the Gauss-Newton process as corrector, to compute the desired vertices. The Jacobian matrix of the mapping is not required at all the vertices but only at the centers of certain local triangulation patches. Several numerical examples show that the method is very efficient in computing triangulations, even around singularities such as limit points and bifurcation points. This opens up new possibilities for determining the form and special features of such solution manifolds.Dedicated to Professor Ivo Babuka on the occasion of his sixtieth birthdayThis work was supported in part by the National Science Foundation under Grant DCR-8309926, the Office of Naval Research under contract N-00014-80-C-9455, and the Air Force Office of Scientific Research under Grant 84-0131     

Efficient construction of a small hitting set for combinatorial rectangles in high dimension

We describe a deterministic algorithm which, on input integersd, m and real number (0,1), produces a subset S of [m] ^d ={1,2,3,...,m} ^d that hits every combinatorial rectangle in [m] ^d of volume at least , i.e., every subset of [m] ^d the formR ₁×R ₂×...×R _d of size at least m ^d . The cardinality of S is polynomial inm(logd)/, and the time to construct it is polynomial inmd/. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables.A preliminary version of this paper appeared in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993.Research partially done while visiting the International Computer Science Institute. Research supported in part by a grant from the Israel-USA Binational Science Foundation.A large portion of this research was done while still at the International Computer Science Institute in Berkeley, California. Research supported in part by National Science Foundation operating grants CCR-9304722 and NCR-9416101, and United States-Israel Binational Science Foundation grant No. 92-00226.Supported in part by NSF under grants CCR-8911388 and CCR-9215293 and by AFOSR grants AFOSR-89-0512 AFOSR-90-0008, and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology. Research partially done while visiting the International Computer Science Institute.Partially supported by NSF NYI Grant No. CCR-9457799. Most of this research was done while the author was at MIT, partially supported by an NSF Postdoctoral Fellowship. Research partially done while visiting the International Computer Science Institute.     

Castles in the air revisited

We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ ^d isO(n ^d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more than one “side” isO(n ^d−1 logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n ^d−1 log² n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement. Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.