Algorithms for minimum length partitions of polygons

We show that it is possible to find a diagonal partition of anyn-vertex simple polygon into smaller polygons, each of at mostm edges, minimizing the total length of the partitioning diagonals, in timeO(n ³ m ²). We derive the same asymptotic upper time-bound for minimum length diagonal partitions of simple polygons into exactlym-gons provided that the input polygon can be partitioned intom-gons. Also, in the latter case, if the input polygon is convex, we can reduce the upper time-bound toO(n ³ logm).     

A Discrete Isoperimetric Problem

We prove that the perimeter of any convex n-gons of diameter 1 is at most n2nsin (/2n). Equality is attained here if and only if n has an odd factor. In the latter case, there are (up to congruence) only finitely many extremal n-gons. In fact, the convex n-gons of diameter 1 and perimeter n2n sin (/2n) are in bijective correspondence with the solutions of a diophantine problem.     

Diameter graphs of polygons and the proof of a conjecture of Graham

We show that for an n-gon with unit diameter to have maximum area, its diameter graph must contain a cycle, and we derive an isodiametric theorem for such n-gons in terms of the length of the cycle. We then apply this theorem to prove Graham's 1975 conjecture that the diameter graph of a maximal 2m-gon (m?3) must be a cycle of length 2m−1 with one additional edge attached to it.     

The two-convex-polygons TSP: A solvable case

In this paper, the Travelling Salesman Problem whenm points are on one convex polygonP, andn points are on another convex polygonQ, insideP, is polynomially solved. For this specific case, anO(m ³ n ³) time andO(m ² n ²) space algorithm to obtain the tour with minimum length is provided.     

Affinely Regular Polygons as Extremals of Area Functionals

For any convex n-gon P we consider the polygons obtained by dropping a vertex or an edge of P. The area distance of P to such (n−1)-gons, divided by the area of P, is an affinely invariant functional on n-gons whose maximizers coincide with the affinely regular polygons. We provide a complete proof of this result. We extend these area functionals to planar convex bodies and we present connections with the affine isoperimetric inequality and parallel X-ray tomography.     

A density theorem for (multiplicity,rank) pairs

For measure-preserving dynamical systems, we investigate the possible values of the pair (m, r), wherer is the maximal number of Rokhlin towers approximating the system andm is the maximal number of cyclic spaces approximating the associated unitary operator. We prove that in this way we can get every pair (d, n) for everyn≥3, and every divisord of some arithmetic function ψ(n) related to the Euler function. We show that for fixedn, the set of possibled is of density one.     

A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm

Recently, É. Tardos gave a strongly polynomial algorithm for the minimum-cost circulation problem and solved the open problem posed in 1972 by J. Edmonds and R.M. Karp. Her algorithm runs in O(m ² T(m, n) logm) time, wherem is the number of arcs,n is the number of vertices, andT(m, n) is the time required for solving a maximum flow problem in a network withm arcs andn vertices. In the present paper, taking an approach that is a dual of Tardos's, we also give a strongly polynomial algorithm for the minimum-cost circulation problem. Our algorithm runs in O(m ² S(m, n) logm) time and reduces the computational complexity, whereS(m, n) is the time required for solving a shortest path problem with a fixed origin in a network withm arcs,n vertices, and a nonnegative arc length function. The complexity is the same as that of Orlin's algorithm, recently developed by efficiently implementing the Edmonds-Karp scaling algorithm.     

Rotatingn-gon/kn-gon vortex configurations

Summary We demonstrate the existence of stationary point-vortex configurations consisting ofk vortexn-gons and a vortexkn-gon. These configurations exist only for specific values of the vortex strengths; the relative vortex strengths of such a consiguration can be uniquely expressed as functions of the radii of the polygons. Thekn-gon must be oriented so as to be fixed by any reflection fixing one of then-gons; for sufficiently smallk, we show that then-gons must be oriented in such a way that the entire configuration shares the symmetries of any of then-gons. Necessary conditions for the formal stability of general stationary point-vortex configurations set conditions on the vortex strengths. We apply these conditions to then-gon/kn-gon configurations and carry out a complete linear and formal stability analysis in the casek=n=2, showing that linearly and nonlinearly orbitally stable configurations exist.     

On the number of edge disjoint cliques in graphs of given size

In this paper, we prove that any graph ofn vertices andt _r–1(n)+m edges, wheret _r–1(n) is the Turán number, contains (1–o(1)m edge disjointK _r'sifm=o(n ²). Furthermore, we determine the maximumm such that every graph ofn vertices andt _r–1(n)+m edges containsm edge disjointK _r's ifn is sufficiently large.Research partially supported by Hungarian National Foundation for Scientific Research Grant no. 1812.     

Rearrangements of (0–1) matrices

Let ℬ(m) be the set of all then-square (0–1) matrices containingm ones andn ²−m zeros, 0<m<n ². The problem of finding the maximum ofs(A ²) over this set, wheres(A ²) is the sum of the entries ofA ²,A ∈ ℬ (m) is considered. This problem is solved in the particular casesm=n ² −k ² andm=k ²,k ²>(n ²/2). This paper forms part of a thesis in partial fulfillment of the requirements for the degree of Doctor of Science at the Technion-Israel Institute of Technology. The author wishes to thank Professor B. Schwarz and Dr. D. London for their help in the preparation of this paper.     

Feuerbach's relation and Ptolemy's theorem in R n

Ptolemy's equality for four points on a circle is related to a Feuerbach-type area relation. This suggested an extension of Ptolemy's inequality to a Feuerbach type volume relation between simplexes formed from n+2 points in R ⁿ (n2). Extensions of the Möbius-Neuberg and Pompeiu Theorems in R ² are given for R ⁿ . Ptolemy's inequality is also extended to convex n-gons in R ² yielding an extension of Fuhrmann's hexagon theorem to 2n-gons in R ² (n3).     

Efficient Preprocessing of Simple Binary Pattern Forests

Multipattern matching in trees is fundamental to a variety of programming language systems. A bottleneck in this connection has been the combinatorial problem of constructing the immediate subsumption tree for a simple binary pattern forest. We reduce the complexity of this problem fromO(n²) time andO(n²) space toO(n log n) time andO(n) space. Such a result was conjectured possible in 1982 by C. Hoffmann and J. O'Donnell (J. Assoc. Comput. Mach.29(1) (1982), 68–95) and in 1992 finding it was called a main open problem by J. Cai, R. Paige, and R. Tarjan (J. Theoret. Comput. Sci.106(1992), 21–60).     

Bounds on the convex label number of trees

A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that wheneverx, y andz are the labels of vertices on a path of length 2 theny≦(x+z)/2. In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a treeT is the smallest integerm such thatT has a convex labelling with no label greater thanm. We prove that every rooted tree (and hence every tree) withn vertices has convex label number less than 4n. We also exhibitn-vertex trees with convex label number 4n/3+o(n), andn-vertex rooted trees with convex label number 2n +o(n). The research by M. B. and A. W. was partly supported by NSF grant MCS—8311422.     

The number of nearest and farthest points to a compactum in Euclidean space

A typical (in the sense of Baire category) compactA inE, whereE is either the Euclidean spaceE ⁸,s≧2, or the separable Hilbert space ℍ, generates a dense subsetC ^n,m(A) of the underlying space, such that everyx∈C ^n,m(A) has exactlyn nearest andm farthest points fromA, whenevern andm are positive integers satisfyingn+m≦ dimE+2. Research of this author is in part supported by Consiglio Nazionale delle Ricerche, G.N.A.F.A., Italy.     

A primal simplex algorithm that solves the maximum flow problem in at mostnm pivots and O(n 2 m) time

We propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that isclosest to the source node from amongst all possible candidates. We prove that this algorithm requires at mostnm pivots to solve a problem withn nodes andm arcs, and give implementations of it which run in O(n ² m) time. Our algorithm is, as far as we know, the first strongly polynomial primal simplex algorithm for solving the maximum flow problem.This research was supported in part by NSF Grants DMS 85-12277 and CDR 84-21402 and ONR Contract N00014-87-K0214.     

Distance-j-Ovoids in Regular Near 2d-Gons

In [8] valuations were introduced and it was shown that these were important objects for classifying near 2n-gons. Several classes were given including one arising from so-called distance-2j-ovoids. Here we introduce pseudo-valutions and explain why these objects can be important for classifying near (2n+1)-gons. Every valuation of a near polygon gives rise to pseudo-valuations and almost all known examples of pseudo-valuations arise in this way. We show that every distance-(2j+1)-ovoid gives rise to a pseudo-valuation which does not come from a valuation. Subsequently, we study distance-j-ovoids in regular near polygons. We are able to calculate the number of elements of a distance-j-ovoid in two ways, yielding a relation between the parameters of the regular near polygon. We will discuss some cases where this relation can be solved. Postdoctoral Fellow of the Research Foundation - Flanders     

AnO(m + n log n) Algorithm for the Maximum-Clique Problem in Circular-Arc Graphs

We present an algorithm to compute, inO(m + n log n) time, a maximum clique in circular-arc graphs (withnvertices andmedges) provided a circular-arc model of the graph is given. If the circular-arc endpoints are given in sorted order, the time complexity isO(m). The algorithm operates on the geometric structure of the circular arcs, radially sweeping their endpoints; it uses a very simple data structure consisting of doubly linked lists. Previously, the best time bound for this problem wasO(m log log n + n log n), using an algorithm that solved an independent subproblem for each of thencircular arcs. By using the radial-sweep technique, we need not solve each of these subproblems independently; thus we eliminate the log log nfactor from the running time of earlier algorithms. For vertex-weighted circular-arc graphs, it is possible to use our approach to obtain anO(m log log n + n log n) algorithm for finding a maximum-weight clique—which matches the best known algorithm.     

THE MINIMUM AREA OF A SIMPLE POLYGON WITH GIVEN SIDE LENGTHS

Answering a question of H. Harborth, for any given a ₁,...,a _n > 0, satisfying we determine the infimum of the areas of the simple n-gons in the Euclidean plane, having sides of length a ₁,...,a _n (in some order). The infimum is attained (in limit) if the polygon degenerates into a certain kind of triangle, plus some parts of zero area. We show the same result for simple polygons on the sphere (of not too great length), and for simple polygons in the hyperbolic plane. Replacing simple n-gons by convex ones, we answer the analogous questions. The infimum is attained also here for degeneration into a certain kind of triangle. This revised version was published online in August 2006 with corrections to the Cover Date.     

Complexes of graph homomorphisms

Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that Hom(K _m, K_n) is homotopy equivalent to a wedge of (n−m)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graphG, and integersm≥2 andk≥−1, we have ϖ ₁ ^k (Hom(K _m, G))≠0, thenχ(G)≥k+m; here ℤ₂-action is induced by the swapping of two vertices inK _m, and ϖ₁ is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K _n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K _n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm.