共查询到20条相似文献,搜索用时 62 毫秒
1.
The star unfolding of a convex polytope with respect to a pointx on its surface is obtained by cutting the surface along the shortest paths fromx to every vertex, and flattening the surface on the plane. We establish two main properties of the star unfolding:
These two properties permit conceptual simplification of several algorithms concerned with shortest paths on polytopes, and
sometimes a worst-case complexity improvement as well:
相似文献
1. | It does not self-overlap: it is a simple polygon. |
2. | The ridge tree in the unfolding, which is the locus of points with more than one shortest path fromx, is precisely the Voronoi diagram of the images ofx, restricted to the unfolding. |
• | The construction of the ridge tree (in preparation for shortest-path queries, for instance) can be achieved by an especially simpleO(n 2) algorithm. This is no worst-case complexity improvement, but a considerable simplification nonetheless. |
• | The exact set of all shortest-path “edge sequences” on a polytope can be found by an algorithm considerably simpler than was known previously, with a time improvement of roughly a factor ofn over the old bound ofO(n 7 logn). |
• | The geodesic diameter of a polygon can be found inO(n 9 logn) time, an improvement of the previous bestO(n 10) algorithm. |
2.
Mahlon M. Day 《Israel Journal of Mathematics》1972,13(3-4):277-280
A geometric consequence inB of local uniform rotundity inB
* is used to prove Asplund’s theorem on Fréchet differentiability of convex functionals. 相似文献
3.
Marie-Claude Arnaud 《Annales Henri Poincare》2008,9(5):881-926
In this article, we prove different results concerning the regularity of the C
0-Lagrangian invariant graphs of the Tonelli flows. For example :
Submitted: July 23, 2007. Accepted: February 14, 2008. 相似文献
• | in dimension 2 and in the autonomous generic case, we prove that such a graph is in fact C 1 on some set with (Lebesgue) full measure; |
• | under certain dynamical additional hypothesis, we prove that these graphs are C 1. |
Résumé. Dans cet article, on démontre différents résultats concernant la régularité des graphes C 0-lagrangiens invariants par des flots de Tonelli. Par exemple :
• en dimension 2, dans le cas autonome et générique, on montre que ces graphes sont de classe C 1 sur un ensemble de mesure (de Lebesque) pleine; • sous certaines hypothèses concernant la dynamique restreinte, on montre que ces graphes sont de classe C 1.
Submitted: July 23, 2007. Accepted: February 14, 2008. 相似文献
4.
Laurent Bartholdi 《Israel Journal of Mathematics》2006,154(1):93-139
We develop the theory of “branch algebras”, which are infinite-dimensional associative algebras that are isomorphic, up to
taking subrings of finite codimension, to a matrix ring over themselves. The main examples come from groups acting on trees.
In particular, for every field
% MathType!End!2!1! we contruct a
% MathType!End!2!1! which
The author acknowledges support from TU Graz and UC Berkeley, where part of this research was conducted. 相似文献
– | • is finitely generated and infinite-dimensional, but has only finitedimensional quotients; |
– | • has a subalgebra of finite codimension, isomorphic toM 2(k); |
– | • is prime; |
– | • has quadratic growth, and therefore Gelfand-Kirillov dimension 2; |
– | • is recursively presented; |
– | • satisfies no identity; |
– | • contains a transcendental, invertible element; |
– | • is semiprimitive if % MathType!End!2!1! has characteristic ≠2; |
– | • is graded if % MathType!End!2!1! has characteristic 2; |
– | • is primitive if % MathType!End!2!1! is a non-algebraic extension of % MathType!End!2!1!; |
– | • is graded nil and Jacobson radical if % MathType!End!2!1! is an algebraic extension of % MathType!End!2!1!. |
5.
John W. Snow 《Algebra Universalis》2005,54(1):65-71
A congruence lattice L of an algebra A is called power-hereditary if every 0-1 sublattice of Ln is the congruence lattice of an algebra on An for all positive integers n. Let A and B be finite algebras. We prove
Received November 11, 2004; accepted in final form November 23, 2004. 相似文献
• | If ConA is distributive, then every subdirect product of ConA and ConB is a congruence lattice on A × B. |
• | If ConA is distributive and ConB is power-hereditary, then (ConA) × (ConB) is powerhereditary. |
• | If ConA ≅ N5 and ConB is modular, then every subdirect product of ConA and ConB is a congruence lattice. |
• | Every congruence lattice representation of N5 is power-hereditary. |
6.
F. G. Timmesfeld 《Archiv der Mathematik》2002,79(6):404-407
Let Φ be a root system of typeA
ℓ, ℓ ≧ 2,D
ℓ, ℓ ≧ 4 orE
ℓ, 6 ≧ ℓ ≧ 8 andG a group generated by nonidentity abelian subgroupsA
r,r∈Φ, satisfying:
Then it is shown, using [3], thatG is a central product of Lie-type groups corresponding to a decomposition of Φ into root-subsystems. 相似文献
(i) | [A r, As]=1 ifs≠−r and ∉ Φ, |
(ii) | [A r, As]≦A r+s ifr+s∈Φ, |
(iii) | X r=〈Ar, A−r〉 is a rank one group. |
7.
In the framework of dynamic programming we provide two results:
This research was supported by the fund for the promotion of research in the technion. 相似文献
| An example where uniform convergence of theT-stage value does not imply equality of the limit and the lower infinite value. |
| Generalized Tauberian theorems, that relate uniform convergence of theT-stage value to uniform convergence of values associated with a general distribution on stages. |
8.
Joseph Corneli Neil Hoffman Paul Holt George Lee Nicholas Leger Stephen Moseley Eric Schoenfeld 《Journal of Geometric Analysis》2007,17(2):189-212
We prove the double bubble conjecture in the three-sphereS
3 and hyperbolic three-spaceH
3 in the cases where we can apply Hutchings theory:
A balancing argument and asymptotic analysis reduce the problem inS
3 andH
3 to some computer checking. The computer analysis has been designed and fully implemented for both spaces. 相似文献
– | • InS 3, when each enclosed volume and the complement occupy at least 10% of the volume ofS 3. |
– | • inH 3, when the smaller volume is at least 85% that of the larger. |
9.
10.
We address the structure of nonconvex closed subsets of the Euclidean plane. A closed subsetS⊆ℝ2 which is not presentable as a countable union of convex sets satisfies the following dichotomy:
We also show that iff: [N]2→{0, 1} is a continuous coloring of pairs, and no open subset ofN isf-monochromatic, then the least numberκ off-monochromatic sets required to coverN satisfiesK
+>-c. Consequently, a closed subset of ℝ2 that cannot be covered by countably many convex subsets, cannot be covered by any number of convex subsets other than the
continuum or the immediate predecessor of the continuum. The analogous fact is false for closed subsets of ℝ3. 相似文献
(1) | There is a perfect nonemptyP⊆S so that |C∩P|<3 for every convexC⊆S. In this case coveringS by convex subsets ofS is equivalent to coveringP by finite subsets, hence no nontrivial convex covers ofS can exist. |
(2) | There exists a continuous pair coloringf: [N]2→{0, 1} of the spaceN of irrational numbers so that coveringS by convex subsets is equivalent to coveringN byf-monochromatic sets. In this case it is consistent thatS has a convex cover of cardinality strictly smaller than the continuumc in some forcing extension of the universe. |
11.
We present a new pivot-based algorithm which can be used with minor modification for the enumeration of the facets of the
convex hull of a set of points, or for the enumeration of the vertices of an arrangement or of a convex polyhedron, in arbitrary
dimension. The algorithm has the following properties:
For example, the algorithm finds thev vertices of a polyhedron inR
d defined by a nondegenerate system ofn inequalities (or, dually, thev facets of the convex hull ofn points inR
d, where each facet contains exactlyd given points) in timeO(ndv) andO(nd) space. Thev vertices in a simple arrangement ofn hyperplanes inR
d can be found inO(n
2
dv) time andO(nd) space complexity. The algorithm is based on inverting finite pivot algorithms for linear programming. 相似文献
(a) | Virtually no additional storage is required beyond the input data. |
(b) | The output list produced is free of duplicates. |
(c) | The algorithm is extremely simple, requires no data structures, and handles all degenerate cases. |
(d) | The running time is output sensitive for nondegenerate inputs. |
(e) | The algorithm is easy to parallelize efficiently. |
12.
LetK be a class of spaces which are eigher a pseudo-opens-image of a metric space or ak-space having a compact-countable closedk-network. LetK′ be a class of spaces which are either a Fréchet space with a point-countablek-network or a point-G
δ
k-space having a compact-countablek-network. In this paper, we obtain some sufficient and necessary conditions that the products of finitely or countably many
spaces in the classK orK′ are ak-space. The main results are that
Project supported by the Mathematical Tianyuan Foundation of China 相似文献
Theorem A | If X, Y∈K. Then X x Y is a k-space if and only if (X, Y) has the Tanaka's condition. |
Theorem B | The following are equivalent: |
(a) | BF(ω 2)is false. |
(b) | For each X, Y ∈ K′, X x Y is a k-space if and only if (X,Y) has the Tanaka's condition. |
13.
M. Rovinsky 《Selecta Mathematica, New Series》2009,15(2):343-376
Let G be the automorphism group of an extension of algebraically closed fields of characteristic zero of transcendence degree n, 1 ≤ n ≤ ∞. In this paper we
The study of open subgroups is motivated by the study of (the stabilizers of) smooth representations undertaken in [R1, R3].
The functor Γ is an analogue of the global sections functor on the category of sheaves on a smooth proper algebraic variety.
Another result is that ‘interesting’ semilinear representations are ‘globally generated’.
相似文献
• | construct some maximal closed non-open subgroups Gv, and some (all, in the case of countable transcendence degree) maximal open proper subgroups of G; |
• | describe, in the case of countable transcendence degree, the automorphism subgroups over the intermediate subfields (a question of Krull, [K2, §4, question 3b)]); |
• | construct, in the case n = ∞, a fully faithful subfunctor ( − )v of the forgetful functor from the category of smooth representations of G to the category of smooth representations of Gv; |
• | construct, using the functors ( − )v, a subfunctor Γ of the identity functor on , coincident (via the forgetful functor) with the functor Γ on the category of admissible semilinear representations of G constructed in [R3] in the case n = ∞ and . |
14.
Xian Ling FAN 《数学学报(英文版)》2007,23(2):281-288
Let (Ω,μ) be a a-finite measure space and Φ : Ω × [0,∞) → [0, ∞] be a Musielak-Orlicz function. Denote by L^Φ(Ω) the Musielak-Orlicz space generated by Φ. We prove that the Amemiya norm equals the Orlicz norm in L^Φ(Ω). 相似文献
15.
16.
A closed, convex and bounded setP in a Banach spaceE is called a polytope if every finite-dimensional section ofP is a polytope. A Banach spaceE is called polyhedral ifE has an equivalent norm such that its unit ball is a polytope. We prove here:
We deduce from these two results that in a polyhedral Banach space (for instance in c0(ℕ) or inC(K) forK countable compact), every equivalent norm can be approximated by norms which are analytic onE/{0}. 相似文献
(1) | LetW be an arbitrary closed, convex and bounded body in a separable polyhedral Banach spaceE and let ε>0. Then there exists a tangential ε-approximating polytopeP for the bodyW. |
(2) | LetP be a polytope in a separable Banach spaceE. Then, for every ε>0,P can be ε-approximated by an analytic, closed, convex and bounded bodyV. |
17.
Nikita A. Karpenko 《manuscripta mathematica》1995,88(1):109-117
We compute degrees of algebraic cycles on certain Severi-Brauer varieties and apply it to show that:
This article was processed by the author using the LATEX style filecljour 1 from Springer-Verlag 相似文献
– | - a generic division algebra of indexp α and exponentp is not decomposable (in a tensor product of two algebras) for any primep and any α except the case whenp=2 and 2 | α; |
– | - the 2-codimensional Chow group CH2 of the Severi-Brauer variety corresponding to the generic division algebra of index 8 and exponent 2 has a non-trivial torsion. |
18.
We give a necessary and sufficient condition for the uniformly non-l
n
(1)
property of Musielak-Orlicz sequence spacesl
Φ generated by a sequence Φ=(ϕn:n⩾l) of finite Orlicz functions such that
for eachn∈ℕ. As a result, forn
0⩾2, there exist spacesl
Φ which are only uniformly non-l
n
(1)
forn⩾n
0. Moreover we obtain a characterization of uniformly non-l
n
(1)
and reflexive Orlicz sequence spaces over a wide class of purely atomic measures and of uniformly non-l
n
(1)
Nakano sequence spaces. This extends a result of Luxemburg in [19].
Submitted in memory of Professor W. Orlicz 相似文献
19.
GuangYan Jia 《中国科学A辑(英文版)》2009,52(4):785-793
In this paper, we prove that for a sublinear expectation ɛ[·] defined on L
2(Ω,), the following statements are equivalent:
Furthermore, we prove a sandwich theorem for subadditive expectation and superadditive expectation.
This work was supported by National Basic Research Program of China (973 Program) (Grant No. 2007CB814901) (Financial Risk)
and National Natural Science Foundation of China (Grant No. 10671111) 相似文献
(i) | ɛ is a minimal member of the set of all sublinear expectations defined on L 2(Ω,) |
(ii) | ɛ is linear |
(iii) | the two-dimensional Jensen’s inequality for ɛ holds. |
20.
M. K. Sen 《Semigroup Forum》1992,44(1):149-156
A pair (S, P) of a regular semigroupsS and a subsetP ofE
s
whereE
s
is the set of all idempotent elements ofS is called aP-regular semigroupS(P) if it satisfies the following:
The class of orthodox semigroups and the class of regular *-semigroups are within the class ofP-regular semigroups. This paper gives a characterisation of theP-kernel of aP-congruence. 相似文献
(1) | P 2 ⊆E S |
(2) | qPq⊆P for allq∈P |
(3) | for anyx∈S there existsx †∈V(x) (the set of inverses ofx), such thatxP 1 x †⊆P andx † P 1 x⊆P whereP 1=P∩{1}. |