Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

Algorithms for ham-sandwich cuts

Given disjoint setsP ₁,P ₂, ...,P _d inR ^d withn points in total, ahamsandwich cut is a hyperplane that simultaneously bisects theP _i . We present algorithms for finding ham-sandwich cuts in every dimensiond>1. Whend=2, the algorithm is optimal, having complexityO(n). For dimensiond>2, the bound on the running time is proportional to the worst-case time needed for constructing a level in an arrangement ofn hyperplanes in dimensiond−1. This, in turn, is related to the number ofk-sets inR ^d−1 . With the current estimates, we get complexity close toO(n ^3/2 ) ford=3, roughlyO(n ^8/3 ) ford=4, andO(n ^d−1−a(d) ) for somea(d)>0 (going to zero asd increases) for largerd. We also give a linear-time algorithm for ham-sandwich cuts inR ³ when the three sets are suitably separated. A preliminary version of the results of this paper appeared in [16] and [17]. Part of this research by J. Matoušek was done while he was visiting the School of Mathematics, Georgia Institute of Technology, Atlanta, and part of his work on this paper was supported by a Humboldt Research Fellowship. W. Steiger expresses gratitude to the NSF DIMACS Center at Rutgers, and his research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio

We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = (d ²), the expected total number of major Karmarkar's iterations is O(d ²(logn)L), compared to the best known deterministic bound of O( L). We also present several other results which follow from the general scheme.     

Applications of random sampling in computational geometry,II

We use random sampling for several new geometric algorithms. The algorithms are Las Vegas, and their expected bounds are with respect to the random behavior of the algorithms. These algorithms follow from new general results giving sharp bounds for the use of random subsets in geometric algorithms. These bounds show that random subsets can be used optimally for divide-and-conquer, and also give bounds for a simple, general technique for building geometric structures incrementally. One new algorithm reports all the intersecting pairs of a set of line segments in the plane, and requiresO(A+n logn) expected time, whereA is the number of intersecting pairs reported. The algorithm requiresO(n) space in the worst case. Another algorithm computes the convex hull ofn points inE ^d inO(n logn) expected time ford=3, andO(n ^[d/2]) expected time ford>3. The algorithm also gives fast expected times for random input points. Another algorithm computes the diameter of a set ofn points inE ³ inO(n logn) expected time, and on the way computes the intersection ofn unit balls inE ³. We show thatO(n logA) expected time suffices to compute the convex hull ofn points inE ³, whereA is the number of input points on the surface of the hull. Algorithms for halfspace range reporting are also given. In addition, we give asymptotically tight bounds for (k)-sets, which are certain halfspace partitions of point sets, and give a simple proof of Lee's bounds for high-order Voronoi diagrams.     

Linear Systems of Cubics Singular at General Points of Projective Space

We present an elementary proof that given a general collection of d points in Pⁿ the linear system of cubics singular on each point has the expected codimension except when n=4 and d=7. In that case the cubic is unique. This, together with previous work of the author, gives a proof of the Alexander–Hirschowitz interpolation theorem.     

Randomized algorithms for the separation of point sets and for solving quadratic programs

A randomized algorithm for finding a hyperplane separating two finite point sets in the Euclidean space ^d and a randomized algorithm for solving linearly constrained general convex quadratic problems are proposed. The expected running time of the separating algorithm isO(dd! (m + n)), wherem andn are cardinalities of sets to be separated. The expected running time of the algorithm for solving quadratic problems isO(dd! s) wheres is the number of inequality constraints. These algorithms are based on the ideas of Seidel's linear programming algorithm [6]. They are closely related to algorithms of [8], [2], and [9] and belong to an abstract class of algorithms investigated in [1]. The algorithm for solving quadratic problems has some features of the one proposed in [7].This research was done when the author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of the Russian Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str. 16, Russia.     

Cutting hyperplane arrangements

We consider a collectionH ofn hyperplanes in E ^d (where the dimensiond is fixed). An ε-cutting forH is a collection of (possibly unbounded)d-dimensional simplices with disjoint interors, which cover all E ^d and such that the interior of any simplex is intersected by at mostεn hyperplanes ofH. We give a deterministic algorithm for finding a (1/r)-cutting withO(r ^d ) simplices (which is asymptotically optimal). Forr≤n ^1−σ, where δ>0 is arbitrary but fixed, the running time of this algorithm isO(n(logn) ^O(1) r ^d−1). In the plane we achieve a time boundO(nr) forr≤n ^1−δ, which is optimal if we also want to compute the collection of lines intersecting each simplex of the cutting. This improves a result of Agarwal, and gives a conceptually simpler algorithm. For ann point setX⊆E ^d and a parameterr, we can deterministically compute a (1/r)-net of sizeO(rlogr) for the range space (X, {X ϒ R; R is a simplex}), In timeO(n(logn) ^O(1) r ^d−1 +r ^O(1)). The size of the (1/r)-net matches the best known existence result. By a simple transformation, this allows us to find ε-nets for other range spaces usually encountered in computational geometry. These results have numerous applications for derandomizing algorithms in computational geometry without affecting their running time significantly. A preliminary version of this paper appeared inProceedings of the Sixth ACM Symposium on Computational Geometry, Berkeley, 1990, pp. 1–9. Work on this paper was supported by DIMACS Center.     

A near-linear algorithm for the planar segment-center problem

LetP be a set ofn points in the plane and lete be a segment of fixed length. The segment-center problem is to find a placement ofe (allowing translation and rotation) which minimizes the maximum euclidean distance frome to the points ofP. We present an algorithm that solves the problem in timeO(n ^1+ε), for any ε>0, improving the previous solution of Agarwalet al. [3] by nearly a factor ofO(n). Work on this paper by the second author has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, 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.     

Recurrence Relationships for the Mean Number of Faces and Vertices for Random Convex Hulls

This paper studies the convex hull of n random points in R^d\mathsf{R}^{d} . A recently proved topological identity of the author is used in combination with identities of Efron and Buchta to find the expected number of vertices of the convex hull—yielding a new recurrence formula for all dimensions d. A recurrence for the expected number of facets and (d−2)-faces is also found, this analysis building on a technique of Rényi and Sulanke. Other relationships for the expected count of i-faces (1≤i<d) are found when d≤5, by applying the Dehn–Sommerville identities. A general recurrence identity (see (3) below) for this expected count is conjectured.     

A dual approach to detect polyhedral intersections in arbitrary dimensions

This paper presents a dual approach to detect intersections of hyperplanes and convex polyhedra in arbitrary dimensions. Ind dimensions, the time complexities of the dual algorithms areO(2 ^d logn) for the hyperplane-polyhedron intersection problem, andO((2d) ^d–1 log ^d–1 n) for the polyhedron- polyhedron intersection problem. These results are the first of their kind ford > 3. In two dimensions, these time bounds are achieved with linear space and preprocessing. In three dimensions, the hyperplane-polyhedron intersection problem is also solved with linear space and preprocessing; quadratic space and preprocessing, however, is required for the polyhedron-polyhedron intersection problem. For generald, the dual algorithms require space and preprocessing. All of these results readily extend to unbounded polyhedra.This is an extended and revised version of a paper presented at the 25th Annual Allerton Conference on Communication, Control, and Computing (October 1987). Our work was sponsored by the U.S. Army Research Office (research contract DAAG29-85-0223) and, in the case of the first author, by graduate fellowships from the IBM corporation and the German National Scholarship Foundation.     

Dynamic Euclidean minimum spanning trees and extrema of binary functions

We maintain the minimum spanning tree of a point set in the plane subject to point insertions and deletions, in amortized timeO(n ^1/2 log² n) per update operation. We reduce the problem to maintaining bichromatic closest pairs, which we solve in timeO(n ^e ) per update. Our algorithm uses a novel construction, theordered nearest neighbor path of a set of points. Our results generalize to higher dimensions, and to fully dynamic algorithms for maintaining minima of binary functions, including the diameter of a point set and the bichromatic farthest pair. This research was supported in part by NSF Grant CCR-9258355     

Range Searching and Point Location among Fat Objects

We present a data structure that can store a set of disjoint fat objects ind-space such that point location and bounded-size range searching with arbitrarily shaped ranges can be performed efficiently. The structure can deal with either arbitrary (fat) convex objects or nonconvex (fat) polytopes. The multipurpose data structure supports point location and range searching queries in timeO(log^d−1 n) and requiresO(n log^d−1 n) storage, afterO(n log^d−1 n log log n) preprocessing. The data structure and query algorithm are rather simple.     

Algorithms for shortest paths and d-cycle problems

Let G be a weighted graph with n vertices and m edges. We address the d-cycle problem, i.e., the problem of finding a subgraph of minimum weight with given cyclomatic number d. Hartvigsen [Minimum path bases, J. Algorithms 15 (1993) 125–142] presented an algorithm with running time O(n²m) and O(n^2d−1m²) for the cyclomatic numbers d=1 and d2, respectively. Using a (d+1)-shortest-paths algorithm, we develop a new more efficient algorithm for the d-cycle problem with running time O(n^2d−1+n²m+n³logn).     

Extremal point queries with lines and line segments and related problems

We address a number of extremal point query problems when P is a set of n points in , d3 a constant, including the computation of the farthest point from a query line and the computation of the farthest point from each of the lines spanned by the points in P. In , we give a data structure of size O(n¹⁺), that can be constructed in O(n¹⁺) time and can report the farthest point of P from a query line segment in O(n^2/3+) time, where >0 is an arbitrarily small constant. Applications of our results also include: (1) Sub-cubic time algorithms for fitting a polygonal chain through an indexed set of points in , d3 a constant, and (2) A sub-quadratic time and space algorithm that, given P and an anchor point q, computes the minimum (maximum) area triangle defined by q with P{q}.     

Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

On the expected number of k-sets

Given a setS ofn points inR ^d , a subsetX of sized is called ak-simplex if the hyperplane aff(X) has exactlyk points on one side. We studyE _d (k,n), the expected number of k-simplices whenS is a random sample ofn points from a probability distributionP onR ^d . WhenP is spherically symmetric we prove thatE _d (k, n)≤cn ^d−1 WhenP is uniform on a convex bodyK⊂R ² we prove thatE ₂ (k, n) is asymptotically linear in the rangecn≤k≤n/2 and whenk is constant it is asymptotically the expected number of vertices on the convex hull ofS. Finally, we construct a distributionP onR ² for whichE ₂((n−2)/2,n) iscn logn. The authors express gratitude to the NSF DIMACS Center at Rutgers and Princeton. The research of I. Bárány was supported in part by Hungarian National Science Foundation Grants 1907 and 1909, and W. Steiger's research was supported in part by NSF Grants CCR-8902522 and CCR-9111491.     

VLSI-sorting evaluated under the linear model

There are several different models of computation used on which to base evaluations of VLSI sorting algorithms and there are different measures of complexity. This paper revises complexity results under the linear model that have been gained under the constant model. This approach is due to expected technological development (see Mangir, 1983; Thompson and Raghavan, 1984; Vitanyi, 1984a and Vitanyi, 1984b).For the constant model we know that for medium sized keys there are AT²and AP² optimal sorting algorithms with T ranging from ω(log n) to O(√nk) and P ranging from Ω(1) to O(√nk) (Bilardi, 1984). The main results of asymptotic analysis of sorting algorithms under the linear model are that the lower bounds allow AT² optimal sorting algorithms only for T = Θ(√nk) but allow AP² algorithms in the same range as under the constant model. Furthermore the sorting algorithms presented in this paper meet these lower bounds. This proves that these bounds cannot be improved for k = Θ (log n). The building block for the realization of these sorting algorithms is a comparison exchange module that compares r × s bit matrices in time T_C = Θ(r + s) on an area A_C = Θ(r²) (not including the storage area for the keys).For problem sizes that exceed realistic chip capacities, chip-external sorting algorithms can be used. In this paper two different chip-external sorting algorithms (BBB(S) and TWB(S)) are presented. They are designed to be implemented on a single board. They use a sorting chip S to perform the sort-split operation on blocks of data BBB(S) and TWB(S) are systolic algorithms using local communication only so that their evaluation does not depend on whether the constant or the linear model is used. Furthermore it seems obvious that their design is technically feasible whenever the sorting chip S is technically feasible.TWB has optimal asymptotic time complexity, so its existence proves that under the linear model external sorting can be done asymptotically as fast as under the constant model. The time complexity of TWB(S) is linearly dependent on the speed gs = n_s/t_s. It is shown that the speed if looked at as a function of the chip capacity C is asymptotically maximal for AT² optimal sorting algorithms. Thus S should be a sorting algorithm similar to the M-M-sorter presented in this paper. A major disadvantage of TWB(S) is that it cannot exploit the maximal throughput d_s = n_s/p_s of a systolic sorting algorithm S.Therefore algorithm BBB(S) is introduced. The time complexity of BBB(S) is linearly dependent on d_s. It is shown that the throughput is maximal for AP² optimal algorithms. There is a wide range of such sorting algorithms including algorithms that can be realized in a way that is independent of the length of the keys. For example, BBB(S) with S being a highly parallel version of odd-even transposition sort has this kind of flexibility. A disadvantage of BBB(S) is that it is asymptotically slower than TWB(S).     

Accounting for boundary effects in nearest-neighbor searching

Givenn data points ind-dimensional space, nearest-neighbor searching involves determining the nearest of these data points to a given query point. Most averagecase analyses of nearest-neighbor searching algorithms are made under the simplifying assumption thatd is fixed and thatn is so large relative tod thatboundary effects can be ignored. This means that for any query point the statistical distribution of the data points surrounding it is independent of the location of the query point. However, in many applications of nearest-neighbor searching (such as data compression by vector quantization) this assumption is not met, since the number of data pointsn grows roughly as 2 ^d .Largely for this reason, the actual performances of many nearest-neighbor algorithms tend to be much better than their theoretical analyses would suggest. We present evidence of why this is the case. We provide an accurate analysis of the number of cells visited in nearest-neighbor searching by the bucketing andk-d tree algorithms. We assumem ^dpoints uniformly distributed in dimensiond, wherem is a fixed integer ≥2. Further, we assume that distances are measured in theL _∞ metric. Our analysis is tight in the limit asd approaches infinity. Empirical evidence is presented showing that the analysis applies even in low dimensions. A preliminary version of this paper appeared in theProceedings of the 11th Annual ACM Symposium on Computational Geometry, 1995, pp. 336–344. Part of this research was conducted while the first author was visiting the Max-Planck-Institut für Informatik, Saarbrücken, Germany. The first author was supported by the ESPRIT Basic Research Actions Program, under Contract No. 7141 (project ALCOM II). The support of the National Science Foundation under Grant CCR-9310705 is gratefully acknowledged by the second author. The third author was supported in part by AT&T Bell Laboratories and the Society of Fellows at Harvard University.     

MAXIMAL CALDERON-ZYGMUND SINGULAR INTEGRAL ON RBMO

Given a positive Radon measure μ on R^d satisfying the linear growth condition μ（B（x,r））≤C0r^n,x∈R^d,r〉0,（1） where n is a fixed number and O〈n≤d. When d-1〈n,it is proved that if Tt,N1=0,then the corresponding maximal Calderon-Zygmund singular integral is bounded from RBMO to itself only except that it is infinite μ-a. e. on R^d.     

Pseudo-dimension and entropy of manifolds formed by affine-invariant dictionary

We consider the manifolds H _n(φ) formed by all possible linear combinations of n functions from the set {φ(A⋅+b)}, where x→Ax+b is arbitrary affine mapping in the space ℝ^d. For example, neural networks and radial basis functions are the manifolds of type H _n(φ). We obtain estimates for pseudo-dimension of the manifold H _n(φ) for wide collection of the generator function φ. The estimates have the order O(d ² n) in degree scale, that is the order is proportional to number of parameters of the manifold H _n(φ). Moreover the estimates for ɛ-entropy of the manifold H _n(φ) are obtained. Mathematics subject classifications (2000) 41A46, 41A50, 42A61, 42C10 V. Maiorov: Supported by the Center for Absorption in Science, Ministry of Immigrant Absorption, State of Israel.