A polynomial solution for the potato-peeling problem

The potato-peeling problem asks for the largest convex polygon contained inside a given simple polygon. We give anO(n ⁷) time algorithm to this problem, answering a question of Goodman. We also give anO(n ⁶) time algorithm if the desired polygon is maximized with respect to perimeter.Work in this paper has been supported in part by NSF grants #DCR-84-01898 and #DCR-84-01633, the Office of Naval Research Grant N00014-82-K-0381, and by grants from Digital Equipment Corporation, the Sloan Foundation, the System Development Foundation, and the IBM Corporation. This paper contains the main results of the paper A Polynomial Solution for Potato-Peeling and other Polygon Inclusion and Enclosure Problems presented in the 25th Foundation of Computer Science Conference, 1984, Florida. The second half of that paper is submitted for publication elsewhere [1].     

The maximum number of disjoint pairs in a family of subsets

Let ? be a family of 2 ⁿ⁺¹ subsets of a 2n-element set. Then the number of disjoint pairs in ? is bounded by (1+o(1))2²ⁿ . This proves an old conjecture of Erdös. Let ? be a family of 2^1/(k+1)+δ)n subsets of ann-element set. Then the number of containments in ? is bounded by (1-1/k+o(1))( ₂ ^|?| ). This verifies a conjecture of Daykin and Erdös. A similar Erdös-Stone type result is proved for the maximum number of disjoint pairs in a family of subsets.     

Optimal popular matchings

In this paper we consider the problem of computing an “optimal” popular matching. We assume that our input instance admits a popular matching and here we are asked to return not any popular matching but an optimal popular matching, where the definition of optimality is given as a part of the problem statement; for instance, optimality could be fairness in which case we are required to return a fair popular matching. We show an O(n²+m) algorithm for this problem, assuming that the preference lists are strict, where m is the number of edges in G and n is the number of applicants.     

K-theory of braided tensor ring categories with higher commutativity

We show that theK-theory of a Waldhausen categoryC with anA-ring structure is anA ring spectrum. If theA structure onC supports anE _n structure, so thatBC group completes to ann-fold loop space, thenK (C) is anE _n ring spectrum. In particular, theK-theory of the category of crossedG-sets,G a finite group, is anE ₂ ring spectrum.     

Packing triangles in a graph and its complement

How few edge‐disjoint triangles can there be in a graph G on n vertices and in its complement ? This question was posed by P. Erd?s, who noticed that if G is a disjoint union of two complete graphs of order n/2 then this number is n²/12 + o(n²). Erd?s conjectured that any other graph with n vertices together with its complement should also contain at least that many edge‐disjoint triangles. In this paper, we show how to use a fractional relaxation of the above problem to prove that for every graph G of order n, the total number of edge‐disjoint triangles contained in G and is at least n²/13 for all sufficiently large n. This bound improves some earlier results. We discuss a few related questions as well. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 203–216, 2004     

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.     

A limiting Lagrangian for infinitely constrained convex optimization inR n

For convex optimization inR ⁿ,we show how a minor modification of the usual Lagrangian function (unlike that of the augmented Lagrangians), plus a limiting operation, allows one to close duality gaps even in the absence of a Kuhn-Tucker vector [see the introductory discussion, and see the discussion in Section 4 regarding Eq. (2)]. The cardinality of the convex constraining functions can be arbitrary (finite, countable, or uncountable).In fact, our main result (Theorem 4.3) reveals much finer detail concerning our limiting Lagrangian. There are affine minorants (for any value 0<1 of the limiting parameter ) of the given convex functions, plus an affine form nonpositive onK, for which a general linear inequality holds onR ⁿAfter substantial weakening, this inequality leads to the conclusions of the previous paragraph.This work is motivated by, and is a direct outgrowth of, research carried out jointly with R. J. Duffin.This research was supported by NSF Grant No. GP-37510X1 and ONR Contract No. N00014-75-C0621, NR-047-048. This paper was presented at Constructive Approaches to Mathematical Models, a symposium in honor of R. J. Duffin, Pittsburgh, Pennsylvania, 1978. The author is grateful to Professor Duffin for discussions relating to the work reported here.The author wishes to thank R. J. Duffin for reading an earlier version of this paper and making numerous suggestions for improving it, which are incorporated here. Our exposition and proofs have profited from comments of C. E. Blair and J. Borwein.     

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.     

Weighted Least Square Convergence of Lagrange Interpolation on the Unit Circle

In the paper, a result of Walsh and Sharma on least square convergence of Lagrange interpolation polynomials based on the n-th roots of unity is extended to Lagrange interpolation on the sets obtained by projecting vertically the zeros of (1-x)²=P ^(a,) _n(x),a>0,>0,(1-x)P^(a,) _n(x),a>0,>-1,(1+x)P P^(a,) _n(x),a>-1,0 and P^(a,) _n(x),a>-1,>-1, respectively, onto the unit circle, where P^(a,) _n(x),a>-1,>-1, stands for the n-th Jacobi polynomial. Moreover, a result of Saff and Walsh is also extended.     

Finite-dimensional attainable sets for stochastic control systems

Letx _t ^u () be a stochastic control system on the probability space (, ,P) intoR ⁿ. We say that the pointxR ⁿ is (, ) attainable at timet if there exists an admissible controlu such thatP _xo{x _t ^u ()S (x)}, wherex ₀()=x ₀, 0, 10, andS (x) is the closed Euclidean -ball inR ⁿ centered atx. We define the attainable setA (t) to be the set of all pointsxR ⁿ which are (, ) attainable at timet. For a large class of stochastic control systems, it is shown thatA (t) is compact for eacht and continuous as a function oft in an appropriate metric. From this, the existence of stochastic time-optional controls is established for a large class of nonlinear stochastic differential equations.This research was supported by the National Research Council of Canada, Grant No. A-9072.     

On a nonlinear eigenvalue problem

In the present paper we consider a selfadjoint and nonsmooth operator-valued function on (c, d)R ¹. We suppose that the equation (L()x, x)=0,x0, has exactly one rootp(x) (c, d) and the functionf()=(L()x, x) is increasing at the pointp(x). We discuss questions of the variational theory of the spectrum. Some theorems on the variational properties of the spectrum are proved.     

Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching

We give the solution to the following question of C. D. Godsil[2]: Among the bipartite graphsG with a unique perfect matching and such that a bipartite graph obtains when the edges of the matching are contracted, characterize those having the property thatG ⁺G, whereG ⁺ is the bipartite multigraph whose adjacency matrix,B ⁺, is diagonally similar to the inverse of the adjacency matrix ofG put in lower-triangular form. The characterization is thatG must be obtainable from a bipartite graph by adding, to each vertex, a neighbor of degree one. Our approach relies on the association of a directed graph to each pair (G, M) of a bipartite graphG and a perfect matchingM ofG.     

An efficient algorithm for the “stable roommates” problem

The stable marriage problem is that of matching n men and n women, each of whom has ranked the members of the opposite sex in order of preference, so that no unmatched couple both prefer each other to their partners under the matching. At least one stable matching exists for every stable marriage instance, and efficient algorithms for finding such a matching are well known. The stable roommates problem involves a single set of even cardinality n, each member of which ranks all the others in order of preference. A stable matching is now a partition of this single set into n/2 pairs so that no two unmatched members both prefer each other to their partners under the matching. In this case, there are problem instances for which no stable matching exists. However, the present paper describes an O(n²) algorithm that will determine, for any instance of the problem, whether a stable matching exists, and if so, will find such a matching.     

A random 1-011-011-01algorithm for depth first search

In this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithm is anRNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on aP-RAM. The run time of the algorithm isO(T _MM(n) log³ n), and the number of processors used isP _MM (n) whereT _MM(n) andP _MM(n) are the time and number of processors needed to find a minimum weight perfect matching on ann vertex graph with maximum edge weightn.This research was done while the first author was visiting the Mathematical Research Institute in Berkeley. Research supported in part by NSF grant 8120790.Supported by Air Force Grant AFOSR-85-0203A.     

Constructing disjoint paths on expander graphs

In a typical parallel or distributed computation model processors are connected by a spars interconnection network. To establish open-line communication between pairs of processors that wish to communicate interactively, a set of disjoint paths has to be constructed on the network. Since communication needs vary in time, paths have to be dynamically constructed and destroyed.We study the complexity of constructing disjoint paths between given pairs of vertices on expander interconnection graphs. These graphs have been shown before to possess desirable properties for other communication tasks.We present a sufficient condition for the existence ofKn ^Q edge-disjoint paths connecting any set ofK pairs of vertices on an expander graph, wheren is the number of vertices and<1 is some constant. We then show that the computational problem of constructing these paths lies in the classes Deterministic-P and Random-P C.Furthermore, we show that the set of paths can be constructed in probabilistic polylog time in the parallel-distributed model of computation, in which then participating processors reside in the nodes of the communication graph and all communication is done through edges of the graph. Thus, the disjoint paths are constructed in the very computation model that uses them.Finally, we show how to apply variants of our parallel algorithms to find sets ofvertex-disjoint paths when certain conditions are satisfied.Supported in part by a Weizmann fellowship and by contract ONR N00014-85-C-0731.     

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.     

Norm-graphs and bipartite turán numbers

For everyt>1 and positiven we construct explicit examples of graphsG with |V (G)|=n, |E(G)|c _t ·n ^2–1/t which do not contain a complete bipartite graghK _t,t !+1 This establishes the exact order of magnitude of the Turán numbers ex (n, K _t,s ) for any fixedt and allst!+1, improving over the previous probabilistic lower bounds for such pairs (t, s). The construction relies on elementary facts from commutative algebra.Research supported in part by NSF Grants DMS-8707320 and DMS-9102866.Research supported in part by Hungarian National Foundation for Scientific Research Grant     

Intersection queries in sets of disks

In this paper we develop some new data structures for storing a set of disks that can answer different types of intersection queries efficiency. If the disks are non-intersecting we obtain a linear size data structure that can report allk disks intersecting a query line segment in timeO(n ⁺ +k), wheren is the number of disks,=log₂(1+5)–1 0.695, and is an arbitrarily small positive constant. If the segment is a full line, the query time becomesO(n +k). For intersecting disks we obtain anO(n logn) size data structure that can answer an intersection query in timeO(n ^2/3 log² n+k). We also present a linear size data structure for ray shooting queries, whose query time isO(n ).The research of the first two authors was supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). The work of the third author was supported byDimacs (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center — NSF-STC88-09648.     

Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.