On the dilatation of extremal quasiconformal mappings of polygons

A polygon P _N is the unit disk with distinguished boundary points, . An extremal quasiconformal mapping maps each polygon inscribed in onto a polygon inscribed in . Let f _N be the extremal quasiconformal mapping of P _N onto P' _N. Let K _N be its dilatation and let K ₀ be the maximal dilatation of f ₀. Then, evidently . The problem is, when equality holds. This is completely answered, if f ₀ does not have any essential boundary points. For quadrilaterals Q and Q' = f ₀ (Q) the problem is sup(M'/M) = K ₀, with M and M' the moduli of Q and Q' respectively. Received: December 23, 1997     

Improved Bounds on the Union Complexity of Fat Objects

We introduce a new class of fat, not necessarily convex or polygonal, objects in the plane, namely locally γ-fat objects. We prove that the union complexity of any set of n such objects is O(λ _s+2(n)log ² n). This improves the best known bound, and extends it to a more general class of objects. The research was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301.     

On the Newton polygons of twisted L-functions of binomials

Let χ be an order c multiplicative character of a finite field and $f(x)=x^d+\lambda x^e$ a binomial with $(d,e)=1$. We study the twisted classical and T-adic Newton polygons of f. When $p>(d-e)(2d-1)$, we give a lower bound of Newton polygons and show that they coincide if p does not divide a certain integral constant depending on $p\mathrm{mod}cd$.We conjecture that this condition holds if p is large enough with respect to $c,d$ by combining all known results and the conjecture given by Zhang-Niu. As an example, we show that it holds for $e=d-1$.     

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.     

Pizza again? On the division of polygons into sections with a common origin

The paper explores the division of a polygon into equal-area pieces using line segments originating at a common point. The mathematical background of the proposed method is very simple and belongs to secondary school geometry. Simple examples dividing a square into two, four or eight congruent pieces provide a starting point to discovering how to divide a regular polygon into any number of equal-area pieces using line segments originating from the centre. Moreover, it turns out that there are infinite ways to do the division. Discovering the basic invariant involved allows application of the same procedure to divide any tangential polygon, as after suitable adjustment, it can be used also for rectangles and parallelograms. Further generalization offers many additional solutions of the problem, and some of them are presented for the case of an arbitrary triangle and a square. Links to dynamic demonstrations in GeoGebra serve to illustrate the main results.     

On the complexity of SNP block partitioning under the perfect phylogeny model

Recent technologies for typing single nucleotide polymorphisms (SNPs) across a population are producing genome-wide genotype data for tens of thousands of SNP sites. The emergence of such large data sets underscores the importance of algorithms for large-scale haplotyping. Common haplotyping approaches first partition the SNPs into blocks of high linkage-disequilibrium, and then infer haplotypes for each block separately. We investigate an integrated haplotyping approach where a partition of the SNPs into a minimum number of non-contiguous subsets is sought, such that each subset can be haplotyped under the perfect phylogeny model. We show that finding an optimum partition is -hard even if we are guaranteed that two subsets suffice. On the positive side, we show that a variant of the problem, in which each subset is required to admit a perfect path phylogeny haplotyping, is solvable in polynomial time.     

On the precise growth, covering, and distortion theorems for normalized biholomorphic mappings

In this paper, we consider a normalized biholomorphic mapping f(x) defined on the unit ball in a complex Banach space, where the origin 0 is a zero of order k+1 of f(x)−x. The precise growth and covering theorem for f(x) is obtained when f(x) is a starlike mapping or a starlike mapping of order α. Especially, the precise growth and covering theorem for f(x) is also established when f(x) is a quasi-convex mapping. Moreover, the precise distortion theorem for f(x) is given when f(x) is a convex mapping. Our result includes many known results.     

Axiomatizability and completeness of some classes of partially ordered polygons

We study partially ordered monoids over which a class of free (over sets and over posets), projective, and (strongly, weakly) flat partially ordered polygons is axiomatizable, complete, or model complete. Similar issues for polygons were dealt with in papers by V. Gould and A. Stepanova. Supported by the Council for Grants (under RF President) and State Aid of Leading Scientific Schools (grant NSh-2810.2008.1). Translated from Algebra i Logika, Vol. 48, No. 1, pp. 90–121, January–February, 2009.     

Decay of geometry for Fibonacci critical covering maps of the circle

We study the growth of Dfⁿ(f(c)) when f is a Fibonacci critical covering map of the circle with negative Schwarzian derivative, degree d2 and critical point c of order ℓ>1. As an application we prove that f exhibits exponential decay of geometry if and only if ℓ2, and in this case it has an absolutely continuous invariant probability measure, although not satisfying the so-called Collet–Eckmann condition.     

On interpolation of function spaces by methods defined by means of polygons

We describe the spaces obtained by applying the interpolation methods associated to polygons to N-tuples of weighted L^p-spaces, N-tuples of classical Lorentz spaces and some other N-tuples of function spaces.     

An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices

The multi-vehicle covering tour problem (m-CTP) involves finding a minimum-length set of vehicle routes passing through a subset of vertices, subject to constraints on the length of each route and the number of vertices that it contains, such that each vertex not included in any route lies within a given distance of a route. This paper tackles a particular case of m-CTP where only the restriction on the number of vertices is considered, i.e., the constraint on the length is relaxed. The problem is solved by a branch-and-cut algorithm and a metaheuristic. To develop the branch-and-cut algorithm, we use a new integer programming formulation based on a two-commodity flow model. The metaheuristic is based on the evolutionary local search (ELS) method proposed in [23]. Computational results are reported for a set of test problems derived from the TSPLIB.     

On the covering of syntax-directed translations for context-free grammars

A necessary and sufficient set of conditions is obtained that relates any two context-free grammarsG ₁ andG ₂ with the property that wheneverG ₂ left—or right—coversG ₁, the syntax-directed translations (SDT’s) with underlying grammarG ₁ is a subset of those with underlying grammarG ₂. Also the case thatG ₂ left—or right—coversG ₁ but the SDT’s with underlying grammarG ₁ is not a subset of the SDT’s with underlying grammarG ₂ is considered; in this case an algorithm is described to obtain the syntax-directed translation schema (SDTS) with underlying grammarG ₂ to the given SDTS with underlying grammarG ₁, if it exists.     

On the complexity of the bondage and reinforcement problems

Let G=(V,E)$G=(V,E)$ be a graph. A subset D⊆V$D\subseteq V$ is a dominating set if every vertex not in D$D$ is adjacent to a vertex in D$D$. A dominating set D$D$ is called a total dominating set if every vertex in D$D$ is adjacent to a vertex in D$D$. The domination (resp. total domination) number of G$G$ is the smallest cardinality of a dominating (resp. total dominating) set of G$G$. The bondage (resp. total bondage) number of a nonempty graph G$G$ is the smallest number of edges whose removal from G$G$ results in a graph with larger domination (resp. total domination) number of G$G$. The reinforcement (resp. total reinforcement) number of G$G$ is the smallest number of edges whose addition to G$G$ results in a graph with smaller domination (resp. total domination) number. This paper shows that the decision problems for the bondage, total bondage, reinforcement and total reinforcement numbers are all NP-hard.     

On the equipartition of plane convex bodies and convex polygons

In this paper we consider the problem of partitioning a plane compact convex body into equal-area parts, i.e., an equipartition, by means of chords. We prove two basic results that hold with some specific exceptions: (a) When chords are pairwise non-crossing, the dual tree of the partition has to be a path, (b) A convex n-gon admits no equipartition produced by more than n chords having a common interior point.     

On the 0, 1 facets of the set covering polytope

In this paper, we consider inequalities of the form _jx_j , where _j equals 0 or 1, and is a positive integer. We give necessary and sufficient conditions for such inequalities to define facets of the set covering polytope associated with a 0, 1 constraint matrixA. These conditions are in terms of critical edges and critical cutsets defined in the bipartite incidence graph ofA, and are in the spirit of the work of Balas and Zemel on the set packing problem where similar notions were defined in the intersection graph ofA. Furthermore, we give a polynomial characterization of a class of 0, 1 facets defined from chorded cycles of the bipartite incidence graph. This characterization also yields all the 0, 1 liftings of odd-hole inequalities for the simple plant location polytope.Research partially supported by NSF grant ECS-8601660 and AFORS grant 87-0292.     

On the cost of computing roots of polynomials

Recently Smale has obtained probabilistic estimates of the cost of computing a zero of a polynomial using a global version of Newton's method. Roughly speaking, his result says that, with the exception of a set of polynomials where the method fails or is very slow, the cost grows as a polynomial in the degree. He also asked whether similar results hold for PL homotopy methods. This paper gives such a result for a special algorithm of the PL homotopy type devised by Kuhn. Its main result asserts that the cost of computing some zero of a polynomial of degreen to an accuracy of ε (measured by the number of evaluations of the polynomial) grows no faster than O(n ³ log₂(n/ε)). This is a worst case analysis and holds for all polynomials without exception. This work was supported, in part, by National Science Foundation Grant MCS79-10027 and, in part, by a fellowship of the Guggenheim Foundation.     

On the complexity of linear programming under finite precision arithmetic

In this paper we study the complexity of solving linear programs in finite precision arithmetic. This is the normal setup in scientific computation, as digital computers work in finite precision. We analyze two aspects of the complexity: one is the number of arithmetic operations required to solve the problem approximately, and the other is the working precision required to carry out some critical computations safely. We show how the conditioning of the problem instance affects the working precision required and the computational requirements of a classical logarithmic barrier algorithm to approximate the optimal value of the problem within a given tolerance. Our results show that these complexity measures depend linearly on the logarithm of a certain condition measure. We carry out the analysis by looking at how well Newton's Method can follow the central trajectory of the feasible set, and computing error bounds in terms of the condition measure. These results can be interpreted as a theoretical indication of good numerical behavior of the logarithmic barrier method, in the sense that a problem instance twice as hard as the other from the numerical point of view, requires only at most twice as much precision to be solved. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.This research has been supported through grants from Fundación Andes, under agreement C12021/7, and FONDECYT (project number 1930948).