共查询到20条相似文献,搜索用时 10 毫秒
1.
2.
K. Strebel 《Commentarii Mathematici Helvetici》1999,74(1):143-149
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
0 be the maximal dilatation of f
0. Then, evidently . The problem is, when equality holds. This is completely answered, if f
0 does not have any essential boundary points. For quadrilaterals Q and Q' = f
0
(Q) the problem is sup(M'/M) = K
0, with M and M' the moduli of Q and Q' respectively.
Received: December 23, 1997 相似文献
3.
Mark de Berg 《Discrete and Computational Geometry》2008,40(1):127-140
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 2
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. 相似文献
4.
Let χ be an order c multiplicative character of a finite field and a binomial with . We study the twisted classical and T-adic Newton polygons of f. When , we give a lower bound of Newton polygons and show that they coincide if p does not divide a certain integral constant depending on .We conjecture that this condition holds if p is large enough with respect to by combining all known results and the conjecture given by Zhang-Niu. As an example, we show that it holds for . 相似文献
5.
Jim Foster 《Journal of Combinatorial Theory, Series A》2007,114(8):1515-1525
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. 相似文献
6.
Ilya Sinitsky Moshe Stupel Marina Sinitsky 《International Journal of Mathematical Education in Science & Technology》2018,49(2):281-293
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. 相似文献
7.
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. 相似文献
8.
Taishun Liu 《Journal of Mathematical Analysis and Applications》2004,295(2):404-417
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. 相似文献
9.
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. 相似文献
10.
Eduardo Colli Marcio L. do Nascimento Edson Vargas 《Annales de l'Institut Henri Poincaré (C) Analyse Non Linéaire》2009,26(4):869
We study the growth of Dfn(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. 相似文献
11.
We describe the spaces obtained by applying the interpolation methods associated to polygons to N-tuples of weighted Lp-spaces, N-tuples of classical Lorentz spaces and some other N-tuples of function spaces. 相似文献
12.
Minh Hoàng Hà Nathalie Bostel André Langevin Louis-Martin Rousseau 《European Journal of Operational Research》2013
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. 相似文献
13.
R K Shyamasundar 《Proceedings Mathematical Sciences》1979,88(1):1-19
A necessary and sufficient set of conditions is obtained that relates any two context-free grammarsG
1 andG
2 with the property that wheneverG
2 left—or right—coversG
1, the syntax-directed translations (SDT’s) with underlying grammarG
1 is a subset of those with underlying grammarG
2. Also the case thatG
2 left—or right—coversG
1 but the SDT’s with underlying grammarG
1 is not a subset of the SDT’s with underlying grammarG
2 is considered; in this case an algorithm is described to obtain the syntax-directed translation schema (SDTS) with underlying
grammarG
2 to the given SDTS with underlying grammarG
1, if it exists. 相似文献
14.
Let G=(V,E) be a graph. A subset D⊆V is a dominating set if every vertex not in D is adjacent to a vertex in D. A dominating set D is called a total dominating set if every vertex in D is adjacent to a vertex in D. The domination (resp. total domination) number of G is the smallest cardinality of a dominating (resp. total dominating) set of G. The bondage (resp. total bondage) number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with larger domination (resp. total domination) number of G. The reinforcement (resp. total reinforcement) number of G is the smallest number of edges whose addition to 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. 相似文献
15.
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. 相似文献
16.
In this paper, we consider inequalities of the form
jxj , 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. 相似文献
17.
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
3 log2(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. 相似文献
18.
19.
Jorge R. Vera 《Mathematical Programming》1998,80(1):91-123
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). 相似文献