首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Abstract. Analyzing the worst-case complexity of the k -level in a planar arrangement of n curves is a fundamental problem in combinatorial geometry. We give the first subquadratic upper bound (roughly O( nk^ 1-1/(9· 2 s-3 ) ) ) for curves that are graphs of polynomial functions of an arbitrary fixed degree s . Previously, nontrivial results were known only for the case s=1 and s=2 . We also improve the earlier bound for pseudo-parabolas (curves that pairwise intersect at most twice) to O( nk 7/9 log 2/3 k) . The proofs are simple and rely on a theorem of Tamaki and Tokuyama on cutting pseudo-parabolas into pseudo-segments, as well as a new observation for cutting pseudo-segments into pieces that can be extended to pseudo-lines. We mention applications to parametric and kinetic minimum spanning trees.  相似文献   

2.
   Abstract. Analyzing the worst-case complexity of the k -level in a planar arrangement of n curves is a fundamental problem in combinatorial geometry. We give the first subquadratic upper bound (roughly O( nk^ 1-1/(9· 2 s-3 ) ) ) for curves that are graphs of polynomial functions of an arbitrary fixed degree s . Previously, nontrivial results were known only for the case s=1 and s=2 . We also improve the earlier bound for pseudo-parabolas (curves that pairwise intersect at most twice) to O( nk 7/9 log 2/3 k) . The proofs are simple and rely on a theorem of Tamaki and Tokuyama on cutting pseudo-parabolas into pseudo-segments, as well as a new observation for cutting pseudo-segments into pieces that can be extended to pseudo-lines. We mention applications to parametric and kinetic minimum spanning trees.  相似文献   

3.
We establish a new lower bound for the number of sides required for the component curves of simple Venn diagrams made from polygons. Specifically, for any n-Venn diagram of convex k-gons, we prove that k ≥ (2n - 2 - n) / (n (n - 2)). In the process we prove that Venn diagrams of seven curves, simple or not, cannot be formed from triangles. We then give an example achieving the new lower bound of a (simple, symmetric) Venn diagram of seven convex quadrilaterals. Previously Grunbaum had constructed a symmetric 7-Venn diagram of non-convex 5-gons ["Venn Diagrams II", Geombinatorics 2:25-31, 1992].  相似文献   

4.
We consider hyperelliptic curves in characteristic p>2 for which the Hasse-Witt matrix is the zero matrix. For such curves, we establish an upper bound on the genus g, namely g≤(p-1)/2. For g=(p-1)/2, we establish the fact that up to isomorphism, there is precisely one such curve, namely the one given by the equation y2=xp-x. We determine all hyeprelliptic curves of the form y2=xn-x or y2=xn-1 for which the Hasse-Witt matrix is the zero matrix.  相似文献   

5.
We consider the formula size complexity of boolean functions over the base consisting of ∧, ∨, and ¬ gates. In 1961 Subbotovskaya proved that, for any boolean function on n variables, setting all but a randomly chosen ?n variables to randomly chosen constants, reduces the expected complexity of the induced function by at least a factor. This fact was used by Subbotovskaya to derive a lower bound of Ω(n1.5) for the formula size of the parity function, and more recently by Andreev who exhibited at lower bound of ΩC(n2.5/logO(1)(n)) for a function in P. We present the first improvement of Subbotovskaya's result, showing that the expected formual complexity of a function restricted as above is at most an O(?γ) franction of its original complexity, for This allows us to give an improved lower bound of Ω(n2.556…) for Andreev's function. At the time of discovery, this was the best formula lower bound known for any function in NP. © 1993 John Wiley & Sons, Inc.  相似文献   

6.
This paper is devoted to the problem of how close can one get with the n-th Chebyshev numbers of a compact set ?? to the theoretical lower bound cap(??) n . It is shown that for a system of m ?? 2 analytic curves, there is always a subsequence for which the Chebyshev numbers are at least (1 + ??)cap(??) n , while for another subsequence they are at most (1 + O(n ?1/(m?1)))cap(??) n . It is also shown that the last estimate is optimal. We also discuss how well a system of curves can be approximated by lemniscates in Hausdorff metric. The proofs are based on potential theoretical arguments. Simultaneous Diophantine approximation of harmonic measures lies in the background. To achieve the correct rate, a perturbation of the multi-valued complex Green??s function is introduced which makes the n-th power of its exponential single-valued and which allows the construction of Faber-like polynomials on multiply connected domains.  相似文献   

7.
We study here lifts and random lifts of graphs, as defined by Amit and Linial (Combinatorica 22 (2002), 1–18). We consider the Hadwiger number η and the Hajós number σ of ?‐lifts of Kn and analyze their extremal as well as their typical values (that is, for random lifts). When ? = 2, we show that , and random lifts achieve the lower bound (as n → ∞). For bigger values of ?, we show . We do not know how tight these bounds are, and in fact, the most interesting question that remains open is whether it is possible for η to be o(n). When ? < O(log n), almost every ?‐lift of Kn satisfies η = Θ(n) and for , almost surely . For bigger values of ?, almost always. The Hajós number satisfies , and random lifts achieve the lower bound for bounded ? and approach the upper bound when ? grows. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006  相似文献   

8.
We show, with an elementary proof, that the number of halving simplices in a set of n points in ℝ4 in general position is O(n4-2/45). This improves the previous bound of O(n4-1/13^{4}). Our main new ingredient is a bound on the maximum number of halving simplices intersecting a fixed 2-plane.  相似文献   

9.
In a paper in Journal of Algorithms13 (1992), 148-160, Hirschberg and Larmore introduced the traveler′s problem as a subroutine for constructing the B-tree. They gave an O(n5/3 log1/3n) time algorithm for solving the traveler′s problem of size n. In this paper, we improve their time bound to O(n3/2 log n). As a consequence, we build a B-tree in O(n3/2 log2n) time as compared to the O(n5/3 log4/3n) time algorithm of Hirschberg and Larmore.  相似文献   

10.
In this paper, we show that there exist families of curves (defined over an algebraically closed field k of characteristic p>2) whose Jacobians have interesting p-torsion. For example, for every 0≤fg, we find the dimension of the locus of hyperelliptic curves of genus g with p-rank at most f. We also produce families of curves so that the p-torsion of the Jacobian of each fibre contains multiple copies of the group scheme αp. The method is to study curves which admit an action by (ℤ/2)n so that the quotient is a projective line. As a result, some of these families intersect the hyperelliptic locus .  相似文献   

11.
The edges of the random graph (with the edge probabilityp=1/2) can be covered usingO(n 2lnlnn/(lnn)2) cliques. Hence this is an upper bound on the intersection number (also called clique cover number) of the random graph. A lower bound, obtained by counting arguments, is (1–)n 2/(2lgn)2.Research supported in part by ONR Grant N00014-85K0570 and by NSA/MSP Grant MDA904-90-H-4011.  相似文献   

12.
We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set ofn points andm hyperplanes in $\mathbb{R}^d $ , is any point contained in any hyperplane? We define a general class ofpartitioning algorithms, and show that in the worst case, for allm andn, any such algorithm requires time Ω(n logm + n 2/3m2/3 + m logn) in two dimensions, or Ω(n logm + n 5/6m1/2 + n1/2m5/6 + m logn) in three or more dimensions. We obtain slightly higher bounds for the counting version of Hopcroft's problem in four or more dimensions. Our planar lower bound is within a factor of 2O(log*(n+m)) of the best known upper bound, due to Matou?ek. Previously, the best known lower bound, in any dimension, was Ω(n logm + m logn). We develop our lower bounds in two stages. First we define a combinatorial representation of the relative order type of a set of points and hyperplanes, called amonochromatic cover, and derive lower bounds on its size in the worst case. We then show that the running time of any partitioning algorithm is bounded below by the size of some monochromatic cover. As a related result, using a straightforward adversary argument, we derive aquadratic lower bound on the complexity of Hopcroft's problem in a surprisingly powerful decision tree model of computation.  相似文献   

13.
 We prove that for every family of n pairwise intersecting simple closed planar curves in general position, at least (4/5)n 2O(n) points lie on more than one curve. This improves the previous lower bound of (3/4)n 2O(n) due to Richter and Thomassen. Received: March 29, 2000 Final version received: August 30, 2001 RID="*" ID="*" Research supported in part by NSF grant DMS-9970325 Acknowledgments. I thank Bruce Richter for informing me about this problem, Gelasio Salazar for reading a preliminary version of the paper, and a Referee for useful comments. Current Address: Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399, USA. e-mail: mubayi@microsoft.com 1991 Mathematics Subject Classification. 05C35, 52C10  相似文献   

14.
It is shown that, for eachn 2 and k 3, there exist at least 2 n -3 non-isomorphic loops of order 2 n k which are Bol but not Moufang. In most cases this bound can be improved.  相似文献   

15.
We show that the number of incidences between m distinct points and n distinct circles in d, for any d 3, is O(m6/11n9/11(m3/n)+m2/3n2/3+m+n), where (n)=(log n)O((n))2 and where (n) is the inverse Ackermann function. The bound coincides with the recent bound of Aronov and Sharir, or rather with its slight improvement by Agarwal et al., for the planar case. We also show that the number of incidences between m points and n unrestricted convex (or bounded-degree algebraic) plane curves, no two in a common plane, is O(m4/7n17/21+m2/3n2/3+m+n), in any dimension d 3. Our results improve the upper bound on the number of congruent copies of a fixed tetrahedron in a set of n points in 4-space and the lower bound for the number of distinct distances in a set of n points in 3-space. Another application is an improved bound for the number of incidences (or, rather, containments) between lines and reguli in three dimensions. The latter result has already been applied by Feldman and Sharir to obtain a new bound on the number of joints in an arrangement of lines in three dimensions.  相似文献   

16.
We study modified wave operators for the Hartree equation with a long-range potential |x|-n |x|^{-\nu} , extending the result in [12] to the whole range of the Dollard type 1/2 < n \nu < 1. We construct the modified wave operators in the whole space of (1 + |x|)-sL2 (1 + |x|)^{-s}L^2 . We also have the image, strong continuity and strong asymptotic approximation in the same space. The lower bound $ s > 1 - \nu / 2 $ s > 1 - \nu / 2 of the weight is sharp from the scaling argument. Those maps are homeomorphic onto open subsets, which implies in particular asymptotic completeness for small data.  相似文献   

17.
Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n ? 1 so-called ‘blocking flow’ problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n2). Karzanov devised the first O(n2)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n2)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.  相似文献   

18.
Let Γ be a collection of unbounded x -monotone Jordan arcs intersecting at most twice each other, which we call pseudoparabolas, since two axis parallel parabolas intersect at most twice. We investigate how to cut pseudoparabolas into the minimum number of curve segments so that each pair of segments intersect at most once. We give an Ω( n 4/3 ) lower bound and O(n 5/3 ) upper bound on the number of cuts. We give the same bounds for an arrangement of circles. Applying the upper bound, we give an O(n 23/12 ) bound on the complexity of a level in an arrangement of pseudoparabolas, and an O(n 11/6 ) bound on the complexity of a combinatorially concave chain of pseudoparabolas. We also give some upper bounds on the number of transitions of the minimum weight matroid base when the weight of each element changes as a quadratic function of a single parameter. Received January 17, 1996, and in revised form November 7, 1996.  相似文献   

19.
A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log2n+2 where c=(log23−1)−1≈1.71 thereby improving a bound given by Bondy and Jackson [3].  相似文献   

20.
We study some systems of polynomials whose support lies in the convex hull of a circuit, giving a sharp upper bound for their numbers of real solutions. This upper bound is non-trivial in that it is smaller than either the Kouchnirenko or the Khovanskii bounds for these systems. When the support is exactly a circuit whose affine span is ℤn, this bound is 2n+1, while the Khovanskii bound is exponential in n2. The bound 2n+1 can be attained only for non-degenerate circuits. Our methods involve a mixture of combinatorics, geometry, and arithmetic. Part of work done at MSRI was supported by NSF grant DMS-9810361. Work of Sottile is supported by the Clay Mathematical Institute. Sottile and Bihan were supported in part by NSF CAREER grant DMS-0134860. Bertrand is supported by the European research network IHP-RAAG contract HPRN-CT-2001-00271.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号