On Cycles Containing a Given Arc in Regular Multipartite Tournaments

In this paper we prove that if T is a regular n-partite tournament with n≥4, then each arc of T lies on a cycle whose vertices are from exactly κ partite sets for κ=4,5,…,n. Our result, in a sense, generalizes a theorem due to Alspach.     

Computing the link center of a simple polygon

The link center of a simple polygonP is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. Here the link distance between two pointsx, y insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx toy. We prove several geometric properties of the link center and present an algorithm that calculates this set in timeO(n ²), wheren is the number of sides ofP. We also give anO(n logn) algorithm for finding an approximate link center, that is, a pointx such that the maximal link distance fromx to any point inP is at most one more than the value attained from the true link center.Work on this paper by the second author has been supported by National Science Foundation Grant DMS-8501947. Work by the third author has been supported by the Canadian National Science and Engineering Research Council, Grant A0332. Work by the fifth author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the seventh author has been supported by a Killam Senior Research Fellowship from the Canada Council, and work by the ninth author has been supported by the National Science Foundation Grants DCR-84-01898 and DCR-84-01633. 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. Further acknowledgments can be obtained from the tenth author upon request.     

A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm

Existing implementations of Munkres' algorithm for the optimal assignment problem are shown to requireO(n ⁴) time in the worstn×n case. A new implementation is presented which runs in worst-case timeO(n ³) and compares favorably in performance with the algorithm of Edmonds and Karp for this problem.The results of this paper were obtained by the author while at the Department of Computer Science, Cornell University. This work was supported in part by a Vanderbilt University Research Council Grant.     

Diameter,width, closest line pair,and parametric searching

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, anO(n ^1+ε) algorithm for computing the diameter of a point set in 3-space, anO(^8/5+ε) algorithm for computing the width of such a set, and onO(n ^8/5+ε) algorithm for computing the closest pair in a set ofn lines in space. All these algorithms are deterministic. Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

An optimal convex hull algorithm in any fixed dimension

We present a deterministic algorithm for computing the convex hull ofn points inE ^d in optimalO(n logn+n ^⌞d/2⌟ ) time. Optimal solutions were previously known only in even dimension and in dimension 3. A by-product of our result is an algorithm for computing the Voronoi diagram ofn points ind-space in optimalO(n logn+n ^⌜d/2⌝ ) time. This research was supported in part by the National Science Foundation under Grant CCR-9002352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. A preliminary version of this paper has appeared in “An optimal convex hull algorithm and new results on cuttings”,Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science, October 1991, pp. 29–38. The convex hull algorithm given in the present paper, although similar in spirit, is considerably simpler than the one given in the proceedings.     

Some results on 4<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript> designs with clear two-factor interaction components

Clear effects criterion is one of the important rules for selecting optimal fractional factorial designs, and it has become an active research issue in recent years. Tang et al. derived upper and lower bounds on the maximum number of clear two-factor interactions (2fi’s) in 2 ^n−(n−k) fractional factorial designs of resolutions III and IV by constructing a 2 ^n−(n−k) design for given k, which are only restricted for the symmetrical case. This paper proposes and studies the clear effects problem for the asymmetrical case. It improves the construction method of Tang et al. for 2 ^n−(n−k) designs with resolution III and derives the upper and lower bounds on the maximum number of clear two-factor interaction components (2fic’s) in 4 ^m 2 ⁿ designs with resolutions III and IV. The lower bounds are achieved by constructing specific designs. Comparisons show that the number of clear 2fic’s in the resulting design attains its maximum number in many cases, which reveals that the construction methods are satisfactory when they are used to construct 4 ^m 2 ⁿ designs under the clear effects criterion. This work was supported by the National Natural Science Foundation of China (Grant Nos. 10571093, 10671099 and 10771123), the Research Foundation for Doctor Programme (Grant No. 20050055038) and the Natural Science Foundation of Shandong Province of China (Grant No. Q2007A05). Zhang’s research was also supported by the Visiting Scholar Program at Chern Institute of Mathematics.     

A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment

We consider the problem of planning the motion of an arbitraryk-sided polygonal robotB, free to translate and rotate in a polygonal environmentV bounded byn edges. We present an algorithm that constructs a single component of the free configuration space ofB in timeO((kn) ^2+ɛ), for any ɛ>0. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying motion-planning problem, within the same running time. Work on this paper by Dan Halperin has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper by Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Israel Science Fund administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. A preliminary and extended version of the paper has appeared as: D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment,Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 382–391. Part of the work on the paper was carried out while Dan Halperin was at Tel Aviv University.     

Vertical decomposition of arrangements of hyperplanes in four dimensions

We show that, for any collection ℋ ofn hyperplanes in ℜ⁴, the combinatorial complexity of thevertical decomposition of the arrangementA(ℋ) of ℋ isO(n ⁴ logn). The proof relies on properties of superimposed convex subdivisions of 3-space, and we also derive some other results concerning them. Work on this paper by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Leonidas Guibas was also supported by National Science Foundation Grant CCR-9215219. Work by Micha Sharir was also supported by National Science Foundation Grant CCR-91-22103, and by grants from the G.I.F.—the German Isreali Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. Work by Jiří Matouŝek was done while he was visiting Tel Aviv University, and its was partially supported by a Humboldt Research Fellowship. Work on this paper by Dan Halperin was carried out while he was at Tel Aviv University.     

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.     

Independent sets in regular graphs and sum-free subsets of finite groups

It is shown that there exists a function∈(k) which tends to 0 ask tends to infinity, such that anyk-regular graph onn vertices contains at most 2^{(1/2+∈(k))n} independent sets. This settles a conjecture of A. Granville and has several applications in Combinatorial Group Theory. Research supported in part by the United States-Israel Binational Science Foundation and by a Bergmann Memorial Grant.     

Construction of large-scale global minimum concave quadratic test problems

Construction of problems with known global solutions is important for the computational testing of constrained global minimization algorithms. In this paper, it is shown how to construct a concave quadratic function which attains its global minimum at a specified vertex of a polytope inR ^n+k. The constructed function is strictly concave in the variablesx R ⁿ and is linear in the variablesy R ^k. The number of linear variablesk may be much larger thann, so that large-scale global minimization test problems can be constructed by the methods described here.This research was supported by the Computer Science Section of the National Science Foundation under Grant No. MCS-81-01214.     

Entire solutions of certain partial differential equations in<Emphasis Type="Bold">C</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

We describe entire solutions inC ⁿ of non-linear partial differential equations of the form (∂w/∂z _j ) ^k =f(w), wheref is a meromorphic function in the complex plane andk is a positive integer. Supported in part by the National Science Foundation (USA) Grant DMS-0100486.     

Approximating maximum independent sets by excluding subgraphs

An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known toO(n/(logn)²). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strongsimultaneous performance guarantee for the clique and coloring problems.The framework ofsubgraph-excluding algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.A preliminary version of this paper appeared in [9].Supported in part by National Science Foundation Grant CCR-8902522 and PYI Award CCR-9057488.Research done at Rutgers University. Supported in part by Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) fellowship.     

A Note on Hermite and Subelliptic Operators

In this note, we compute the fundamental solution for the Hermite operator with singularity at an arbitrary point y∈R^n. We also apply this result to obtain the fundamental solutions for the Grushin operator in R^2 and the sub-Laplacian in the Heisenberg group Hn.     

<Emphasis Type="Bold">C</Emphasis><Superscript><Emphasis Type="Bold">1,</Emphasis><Emphasis Type="Italic">α</Emphasis></Superscript> regularity for infinity harmonic functions in two dimensions

We propose a new method for showing C ^{1, α} regularity for solutions of the infinity Laplacian equation and provide full details of the proof in two dimensions. The proof for dimensions n ≥ 3 depends upon some conjectured local gradient estimates for solutions of certain transformed PDE. LCE is supported in part by NSF Grant DMS-0500452. OS was supported in part by the Miller Institute for Basic Research in Science, Berkeley.     

Lossless Condensers,Unbalanced Expanders,And Extractors

Trevisan showed that many pseudorandom generator constructions give rise to constructions of explicit extractors. We show how to use such constructions to obtain explicit lossless condensers. A lossless condenser is a probabilistic map using only O(logn) additional random bits that maps n bits strings to poly(logK) bit strings, such that any source with support size K is mapped almost injectively to the smaller domain. Our construction remains the best lossless condenser to date. By composing our condenser with previous extractors, we obtain new, improved extractors. For small enough min-entropies our extractors can output all of the randomness with only O(logn) bits. We also obtain a new disperser that works for every entropy loss, uses an O(logn) bit seed, and has only O(logn) entropy loss. This is the best disperser construction to date, and yields other applications. Finally, our lossless condenser can be viewed as an unbalanced bipartite graph with strong expansion properties. * Much of this work was done while the author was in the Computer Science Division, University of California, Berkeley, and supported in part by a David and Lucile Packard Fellowship for Science and Engineering and NSF NYI Grant No. CCR-9457799. The work was also supported in part by an Alon fellowship and by the Israel Science Foundation. † Much of this work was done while the author was a graduate student in the Computer Science Division, University of California, Berkeley. Supported in part by NSF Grants CCR-9820897, CCF-0346991, and an Alfred P. Sloan Research Fellowship. ‡ Much of this work was done while the author was on leave at the Computer Science Division, University of California, Berkeley. Supported in part by a David and Lucile Packard Fellowship for Science and Engineering, NSF Grants CCR-9912428 and CCR-0310960, NSF NYI Grant CCR-9457799, and an Alfred P. Sloan Research Fellowship.     

The furthest-site geodesic voronoi diagram

We present anO((n+k) log(n+k))-time,O(n+k)-space algorithm for computing the furthest-site Voronoi diagram ofk point sites with respect to the geodesic metric within a simplen-sided polygon.A preliminary version of this paper appeared in theProceedings of the Fourth ACM Symposium on Computational Geometry, 1988. The work of Boris Aronov was supported by an AT&T Bell Laboratories Ph.D. Scholarship. Part of the work was performed while he was at AT&T Bell Laboratories, Murray Hill, NJ, USA. His current address is Computer Science Department, Polytechnic University, Brooklyn, NY 11201, USA.     

Weak Type Endpoint Estimates for Multilinear θ-type Calderon-Zygmund Operators

In this paper, the author discusses the multilinear singular integrals with certain θ-type Calderdn- Zygmund operators and obtain the boundedness from weak H^1 （R^n） to weak L^1 （R^n）.     

A fast line-sweep algorithm for hidden line elimination

Fast hidden line elimination algorithms can be obtained by minor modifications to algorithms developed for reporting intersections of polygons. We show how the same modifications which have been applied to segment trees can be applied to the data structure of Swart and Ladner as well, leading to anO((n+k)logn) time hidden line elimination algorithm (n is the number of boundary edges of the input polygons andk is the number of intersections of the edges on the projection plane). The algorithm improves the fastest previous line-sweep algorithm for the problem by a factorO(logn).This work was supported by the grant Ot 64/4-2 from the Deutsche Forschungsgemeinschaft.On leave from the Department of Computer Science, University of Helsinki, Finland.     

Hammersley's interacting particle process and longest increasing subsequences

Summary In a famous paper [8] Hammersley investigated the lengthL _n of the longest increasing subsequence of a randomn-permutation. Implicit in that paper is a certain one-dimensional continuous-space interacting particle process. By studying a hydrodynamical limit for Hammersley's process we show by fairly “soft” arguments that limn ^′1/2 EL _n =2. This is a known result, but previous proofs [14, 11] relied on hard analysis of combinatorial asymptotics. Research supported by NSF Grant MCS 92-24857 and the Miller Institute for Basic Research in Science Research supported by NSF Grant DMS92-04864