共查询到20条相似文献,搜索用时 62 毫秒
1.
M. Pellegrini 《Discrete and Computational Geometry》1994,12(1):203-221
We show some combinatorial and algorithmic results concerning finite sets of lines and terrains in 3-space. Our main results include:
- An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of the set of lines that can be translated to infinity without intersecting a given finite set ofn lines, wherec is a suitable constant. This bound is almost tight.
- AnO(n 1.5+ε) randomized expected time algorithm that tests whether a directionv exists along which a set ofn red lines can be translated away from a set ofn blue lines without collisions. ε>0 is an arbitrary small but fixed constant.
- An $O(n^3 2^{c\sqrt {\log n} } )$ upper bound on the worst-case complexity of theenvelope of lines above a terrain withn edges, wherec is a suitable constant.
- An algorithm for computing the intersection of two polyhedral terrains in 3-space withn total edges in timeO(n 4/3+ε+k 1/3 n 1+ε+klog2 n), wherek is the size of the output, and ε>0 is an arbitrary small but fixed constant. This algorithm improves on the best previous result of Chazelleet al. [5].
2.
Philip Rabinowitz 《BIT Numerical Mathematics》1989,29(2):347-355
Convergence results for interpolatory product rules for evaluating Cauchy principal value integrals of the form f ?1 1 v(x)f(x)/x ? λ dx wherev is an admissible weight function have been extended to integrals of the form f ?1 1 k(x)f(x)/x ? λ dx wherek is an arbitrary integrable function subject to certain conditions. Further, whereas the above convergence results were shown when the interpolation points were the Gauss points with respect to some admissible weight functionw, they are now shown to hold when the interpolation points are Radau or Lobatto points with respect tow. 相似文献
3.
Uffe Haagerup 《Israel Journal of Mathematics》1987,60(2):199-224
Let ? denote the real function $$\varphi (k) = k\smallint _0^{\pi /2} \frac{{cos^2 t}}{{\sqrt {1 - k^2 sin ^2 t} }}dt, - 1 \leqq k \leqq 1$$ and letK G C be the complex Grothendieck constant. It is proved thatK G C ≦8/π(k 0+1), wherek 0 is the (unique) solution to the equation?(k)=1/8π(k+1) in the interval [0,1]. One has 8/π(k 0+1) ≈ 1.40491. The previously known upper bound isK G C ≦e 1?y ≈ 1.52621 obtained by Pisier in 1976. 相似文献
4.
Jan Brzeziński 《Rendiconti del Circolo Matematico di Palermo》1979,28(2):325-336
At first Cauchy-problem for the equation: \(L[u(X,t)] \equiv \sum\limits_{i = 1}^n {\frac{{\partial ^2 u}}{{\partial x_1^2 }} + \frac{{2v}}{{\left| X \right|^2 }}} \sum\limits_{i = 1}^n {x_i \frac{{\partial u}}{{\partial x_i }} - \frac{{\partial u}}{{\partial t}} = 0} \) wheren≥1,v—an arbitrary constant,t>0,X=(x 1, …, xn)∈E n/{0}, |X|= =(x 1 2 +…+x n 2 )1/2, with 0 being a centre of coordinate system, is studied. Basing on the above, the solution of Cauchy-Nicolescu problem is given which consist in finding a solution of the equationL p [u (X, t)]=0, withp∈N subject the initial conditions \(\mathop {\lim }\limits_{t \to \infty } L^k [u(X,t)] = \varphi _k (X)\) ,k=0, 1,…,p?1 and ?k(X) are given functions. 相似文献
5.
V. É. Geit 《Mathematical Notes》1971,10(5):768-776
We prove the following: for every sequence {Fv}, Fv ? 0, Fv > 0 there exists a functionf such that
- En(f)?Fn (n=0, 1, 2, ...) and
- Akn?k? v=1 n vk?1 Fv?1?Ωk (f, n?1) (n=1, 2, ...).
6.
In our paper we find all functions ${f : \mathbb {R} \times \mathbb {R}^{3} \rightarrow \mathbb {H}}$ and ${g : \mathbb {R}^{3} \rightarrow \mathbb {H}}$ satisfying ${f (r, {\bf v}) f (s, {\bf w}) = -\langle{\bf v},{\bf w}\rangle + f (rs, s{\bf v} + r{\bf w} + {\bf v} \times {\bf w})}$ ${(r, s \in \mathbb {R}, {\bf v},{\bf w} \in \mathbb {R}^{3})}$ , and ${g({\bf v})g({\bf w}) = -\langle{\bf v}, {\bf w}\rangle + g({\bf v} \times {\bf w})}$ $({{\bf v},{\bf w} \in \mathbb {R}^{3}})$ . These functional equations were motivated by the well-known identities for vector products and quaternions, which can be obtained from the solutions f (r, (v 1, v 2, v 3)) = r + v 1 i + v 2 j + v 3 k and g((v 1 ,v 2, v 3)) = v 1 i + v 2 j + v 3 k. 相似文献
7.
To the unconstrained programme of non-convex function, this article give a modified BFGS algorithm associated with the general line search model. The idea of the algorithm is to modify the approximate Hessian matrix for obtaining the descent direction and guaranteeing the efficacious of the new quasi-Newton iteration equationB k +1s k =y k * ,, wherey k * is the sum ofy k andA k s k , andA k is some matrix. The global convergence properties of the algorithm associating with the general form of line search is proved. 相似文献
8.
Eungil Ko 《Integral Equations and Operator Theory》1997,28(4):492-499
In this paper we shall prove that if an operatorT∈L(⊕ 1 2 H) is an operator matrix of the form $$T = \left( {\begin{array}{*{20}c} {T_1 } & {T_2 } \\ 0 & {T_3 } \\ \end{array} } \right)$$ whereT 1 is hyponormal andT 3 k =0, thenT is subscalar of order 2(k+1). Hence non-trivial invariant subspaces are known to exist if the spectrum ofT has interior in the plane as a result of a theorem of Eschmeier and Prunaru (see [EP]). As a corollary we get that anyk-quasihyponormal operators are subscalar. 相似文献
9.
S. B. Stechkin 《Mathematical Notes》1971,10(3):578-584
The following theorem is proved. Let N = h2n-1, where n ≥ 2, h is odd, 1 <-h < 2n, and suppose that v is a positive integer, v ≥ 3,α is a root of the equation $$(v^2 - 4,N) = 1,\left( {\frac{{v - 2}}{N}} \right) = 1,\left( {\frac{{v + 2}}{N}} \right) = - 1$$ . Then for N to be prime, it is necessary and sufficient that sn?2≡0(modN), where Sk+1=S k 2 ? 2 (k = 0, 1...), so=ah+ a?h. For given N, an algorithm is described for the construction of the smallest v satisfying the conditions of this theorem. 相似文献
10.
For ν≥0 let cνk be the k-th positive zero of the cylinder functionC v(t)=J v(t)cosα-Y v(t)sinα, 0≤α>π whereJ ν(t) andY ν(t) denote the Bessel functions of the first and the second kind, respectively. We prove thatC v,k 1+H(x) is convex as a function of ν, ifc νk≥x>0 and ν≥0, whereH(x) is specified in Theorem 1.1. 相似文献
11.
Given a non-singular quadratic form q of maximal Witt index on $V := V(2n+1,\mathbb{F})$ , let Δ be the building of type B n formed by the subspaces of V totally singular for q and, for 1≤k≤n, let Δ k be the k-grassmannian of Δ. Let ε k be the embedding of Δ k into PG(? k V) mapping every point 〈v 1,v 2,…,v k 〉 of Δ k to the point 〈v 1∧v 2∧?∧v k 〉 of PG(? k V). It is known that if $\mathrm{char}(\mathbb{F})\neq2$ then $\mathrm{dim}(\varepsilon_{k})={{2n+1}\choose k}$ . In this paper we give a new very easy proof of this fact. We also prove that if $\mathrm{char}(\mathbb{F}) = 2$ then $\mathrm{dim}(\varepsilon_{k})={{2n+1}\choose k}-{{2n+1}\choose{k-2}}$ . As a consequence, when 1<k<n and $\mathrm{char}(\mathbb{F}) = 2$ the embedding ε k is not universal. Finally, we prove that if $\mathbb{F}$ is a perfect field of characteristic p>2 or a number field, n>k and k=2 or 3, then ε k is universal. 相似文献
12.
Jerry Bebernes Alberto Bressan Victor A. Galaktionov 《NoDEA : Nonlinear Differential Equations and Applications》1996,3(3):269-286
We construct blow-up patterns for the quasilinear heat equation (QHE) $$u_t = \nabla \cdot (k(u)\nabla u) + Q(u)$$ in Ω×(0,T), Ω being a bounded open convex set in ? N with smooth boundary, with zero Dirichet boundary condition and nonnegative initial data. The nonlinear coefficients of the equation are assumed to be smooth and positive functions and moreoverk(u) andQ(u)/u p with a fixedp>1 are of slow variation asu→∞, so that (QHE) can be treated as a quasilinear perturbation of the well-known semilinear heat equation (SHE) $$u_t = \nabla u) + u^p .$$ We prove that the blow-up patterns for the (QHE) and the (SHE) coincide in a structural sense under the extra assumption $$\smallint ^\infty k(f(e^s ))ds = \infty ,$$ wheref(v) is a monotone solution of the ODEf′(v)=Q(f(v))/v p defined for allv?1. If the integral is finite then the (QHE) is shown to admit an infinite number of different blow-up patterns. 相似文献
13.
14.
Suppose that G is a graph and ${f: V (G) \rightarrow \mathbb{N}}$ is a labeling of the vertices of G. Let S(v) denote the sum of labels over all neighbors of the vertex v in G. A labeling f of G is called lucky if ${S(u) \neq S(v),}$ for every pair of adjacent vertices u and v. Also, for each vertex ${v \in V(G),}$ let L(v) denote a list of natural numbers available at v. A list lucky labeling, is a lucky labeling f such that ${f(v) \in L(v),}$ for each ${v \in V(G).}$ A graph G is said to be lucky k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list lucky labeling of G. The lucky choice number of G, η l (G), is the minimum natural number k such that G is lucky k-choosable. In this paper, we prove that for every graph G with ${\Delta \geq 2, \eta_{l}(G) \leq \Delta^2-\Delta + 1,}$ where Δ denotes the maximum degree of G. Among other results we show that for every 3-list assignment to the vertices of a forest, there is a list lucky labeling which is a proper vertex coloring too. 相似文献
15.
Washiela Fish Roland Fray Eric Mwambene 《Central European Journal of Mathematics》2014,12(9):1362-1371
For k ≥ 1, the odd graph denoted by O(k), is the graph with the vertex-set Ω{k}, the set of all k-subsets of Ω = {1, 2, …, 2k +1}, and any two of its vertices u and v constitute an edge [u, v] if and only if u ∩ v = /0. In this paper the binary code generated by the adjacency matrix of O(k) is studied. The automorphism group of the code is determined, and by identifying a suitable information set, a 2-PD-set of the order of k 4 is determined. Lastly, the relationship between the dual code from O(k) and the code from its graph-theoretical complement $\overline {O(k)} $ , is investigated. 相似文献
16.
Let D be a finite and simple digraph with vertex set V(D), and let f: V(D) → {?1, 1} be a two-valued function. If k ≥?1 is an integer and ${\sum_{x \in N^-(v)}f(x) \ge k}$ for each ${v \in V(G)}$ , where N ?(v) consists of all vertices of D from which arcs go into v, then f is a signed total k-dominating function on D. A set {f 1, f 2, . . . , f d } of signed total k-dominating functions on D with the property that ${\sum_{i=1}^df_i(x)\le k}$ for each ${x \in V(D)}$ , is called a signed total (k, k)-dominating family (of functions) on D. The maximum number of functions in a signed total (k, k)-dominating family on D is the signed total (k, k)-domatic number on D, denoted by ${d_{st}^{k}(D)}$ . In this paper we initiate the study of the signed total (k, k)-domatic number of digraphs, and we present different bounds on ${d_{st}^{k}(D)}$ . Some of our results are extensions of known properties of the signed total domatic number ${d_{st}(D)=d_{st}^{1}(D)}$ of digraphs D as well as the signed total domatic number d st (G) of graphs G, given by Henning (Ars Combin. 79:277–288, 2006). 相似文献
17.
In this article, we continue the study of the geometry of k-D’Atri spaces, 1≤k ≤n?1 (n denotes the dimension of the manifold), begun by the second author. It is known that k-D’Atri spaces, k≥1, are related to properties of Jacobi operators R v along geodesics, since she has shown that ${\operatorname{tr}}R_{v}$ , ${\operatorname{tr}}R_{v}^{2}$ are invariant under the geodesic flow for any unit tangent vector v. Here, assuming that the Riemannian manifold is a D’Atri space, we prove in our main result that ${ \operatorname{tr}}R_{v}^{3}$ is also invariant under the geodesic flow if k≥3. In addition, other properties of Jacobi operators related to the Ledger conditions are obtained, and they are used to give applications to Iwasawa type spaces. In the class of D’Atri spaces of Iwasawa type, we show two different characterizations of the symmetric spaces of noncompact type: they are exactly the $\frak{C}$ -spaces, and on the other hand they are k -D’Atri spaces for some k≥3. In the last case, they are k-D’Atri for all k=1,…,n?1 as well. In particular, Damek–Ricci spaces that are k -D’Atri for some k≥3 are symmetric. Finally, we characterize k-D’Atri spaces for all k=1,…,n?1 as the $\frak{SC}$ -spaces (geodesic symmetries preserve the principal curvatures of small geodesic spheres). Moreover, applying this result in the case of 4 -dimensional homogeneous spaces, we prove that the properties of being a D’Atri (1-D’Atri) space, or a 3-D’Atri space, are equivalent to the property of being a k-D’Atri space for all k=1,2,3. 相似文献
18.
Lutz Volkmann 《Aequationes Mathematicae》2013,86(3):279-287
Let G be a graph with vertex set V(G), and let f : V(G) → {?1, 1} be a two-valued function. If k ≥ 1 is an integer and ${\sum_{x\in N[v]} f(x) \ge k}$ for each ${v \in V(G)}$ , where N[v] is the closed neighborhood of v, then f is a signed k-dominating function on G. A set {f 1,f 2, . . . ,f d } of distinct signed k-dominating functions on G with the property that ${\sum_{i=1}^d f_i(x) \le k}$ for each ${x \in V(G)}$ , is called a signed (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed (k, k)-dominating family on G is the signed (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed (k, k)-domatic number, in particular for regular graphs. 相似文献
19.
A height balanced tree is a rooted binary tree T in which for every vertex v∈V(T), the difference b T (v) between the heights of the subtrees, rooted at the left and right child of v is at most one. We show that a height-balanced tree T h of height h is a subtree of the hypercube Q h+1 of dimension h+1, if T h contains a path P from its root to a leaf such that $\mathbf{b}_{T_{h}}(v)=1$ , for every non-leaf vertex v in P. A Fibonacci tree $\mathbb{F}_{h}$ is a height balanced tree T h of height h in which $\mathbf{b}_{\mathbb{F}_{h}}(v)=1$ , for every non-leaf vertex. $\mathbb{F}_{h}$ has f(h+2)?1 vertices where f(h+2) denotes the (h+2)th Fibonacci number. Since f(h)~20.694h , it follows that if $\mathbb{F}_{h}$ is a subtree of Q n , then n is at least 0.694(h+2). We prove that $\mathbb{F}_{h}$ is a subtree of the hypercube of dimension approximately 0.75h. 相似文献
20.
V. P. Orlov 《Mathematical Notes》1977,21(6):428-433
A differential operator ?, arising from the differential expression $$lv(t) \equiv ( - 1)^r v^{[n]} (t) + \sum\nolimits_{k = 0}^{n - 1} {p_k } (t)v^{[k]} (t) + Av(t),0 \leqslant t \leqslant 1,$$ , and system of boundary value conditions $$P_v [v] = \sum\nolimits_{k = 0}^{n_v } {\alpha _{vk} } r^{[k]} (1) = 0.v - 1, \ldots ,\mu ,0 \leqslant \mu< n$$ is considered in a Banach space E. Herev [k](t)=(a(t) d/dt) k v(t)a(t) being continuous fort?0, α(t) >0 for t > 0 and \(\int_0^1 {\frac{{dz}}{{a(z)}} = + \infty ;}\) the operator A is strongly positive in E. The estimates , are obtained for ?: n even, λ varying over a half plane. 相似文献