共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
M. A. Abam M. de Berg M. Farshi J. Gudmundsson 《Discrete and Computational Geometry》2009,41(4):556-582
We introduce the concept of region-fault tolerant spanners for planar point sets and prove the existence of region-fault tolerant
spanners of small size. For a geometric graph
on a point set P and a region F, we define
to be what remains of
after the vertices and edges of
intersecting F have been removed. A
-fault tolerant
t-spanner is a geometric graph
on P such that for any convex region F, the graph
is a t-spanner for
, where
is the complete geometric graph on P. We prove that any set P of n points admits a
-fault tolerant (1+ε)-spanner of size
for any constant ε>0; if adding Steiner points is allowed, then the size of the spanner reduces to
, and for several special cases, we show how to obtain region-fault tolerant spanners of
size without using Steiner points. We also consider fault-tolerant geodesic
t
-spanners: this is a variant where, for any disk D, the distance in
between any two points u,v∈P∖D is at most t times the geodesic distance between u and v in ℝ2∖D. We prove that for any P, we can add
Steiner points to obtain a fault-tolerant geodesic (1+ε)-spanner of size
.
M.A. Abam was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 612.065.307 and by
the MADALGO Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation.
M. de Berg was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301.
M. Farshi was supported by Ministry of Science, Research and Technology of I.R. Iran.
NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital
Economy and the Australian Research Council through the ICT Centre of Excellence program. 相似文献
3.
Saugata Basu 《Discrete and Computational Geometry》2008,40(4):481-503
Let
be an o-minimal structure over ℝ,
a closed definable set, and
the projection maps as depicted below:
For any collection
of subsets of
, and
, let
denote the collection of subsets of
where
. We prove that there exists a constant C=C(T)>0 such that for any family
of definable sets, where each A
i
=π
1(T∩π
2−1(y
i
)), for some y
i
∈ℝ
ℓ
, the number of distinct stable homotopy types amongst the arrangements
is bounded by
while the number of distinct homotopy types is bounded by
This generalizes to the o-minimal setting, bounds of the same type proved in Basu and Vorobjov (J. Lond. Math. Soc. (2) 76(3):757–776,
2007) for semi-algebraic and semi-Pfaffian families. One technical tool used in the proof of the above results is a pair of topological
comparison theorems reminiscent of Helly’s theorem in convexity theory. These theorems might be of independent interest in
the quantitative study of arrangements.
The author was supported in part by NSF grant CCF-0634907. 相似文献
4.
Tomas Ya. Azizov Jussi Behrndt Peter Jonas Carsten Trunk 《Integral Equations and Operator Theory》2009,63(2):151-163
For closed linear operators or relations A and B acting between Hilbert spaces and the concepts of compact and finite rank perturbations are defined with the help of the orthogonal projections P
A
and P
B
in onto the graphs of A and B. Various equivalent characterizations for such perturbations are proved and it is shown that these notions are a natural
generalization of the usual concepts of compact and finite rank perturbations.
Sadly, our colleague and friend Peter Jonas passed away on July, 18th 2007. 相似文献
5.
D. Caro 《Inventiones Mathematicae》2007,170(3):507-539
Résumé Soient un anneau de valuation discrète complet d’inégales caractéristiques, de corps résiduel parfait k, un -schéma formel propre et lisse, T un diviseur de la fibre spéciale P de , U l’ouvert de P complémentaire de T, Y un sous-k-schéma fermé lisse de U. Nous prouvons que la catégorie des F-isocristaux surconvergents sur Y est équivalente à celle des F-isocristaux surcohérents sur Y (voir [Car, 6.2.1 et 6.4.3.a)]). Plus généralement, nous établissons par recollement une telle équivalence pour tout k-schéma séparé lisse Y. Nous vérifions de plus que les F-complexes de -modules à cohomologie bornée et -surcohérente se dévissent en F-isocristaux surconvergents. 相似文献
6.
7.
Let be a field and q be a nonzero element of that is not a root of unity. We give a criterion for 〈0〉 to be a primitive ideal of the algebra of quantum matrices. Next, we describe all height one primes of ; these two problems are actually interlinked since it turns out that 〈0〉 is a primitive ideal of whenever has only finitely many height one primes. Finally, we compute the automorphism group of in the case where m ≠ n. In order to do this, we first study the action of this group on the prime spectrum of . Then, by using the preferred basis of and PBW bases, we prove that the automorphism group of is isomorphic to the torus when m ≠ n and (m,n) ≠ (1, 3),(3, 1).
This research was supported by a Marie Curie Intra-European Fellowship within the 6th European Community Framework Programme
and by Leverhulme Research Interchange Grant F/00158/X. 相似文献
8.
Bent functions have many applications in the fields of coding theory, communications and cryptography. This paper studies
the constructions of bent functions having the form
for odd n and
for even n, over the finite field
of odd characteristic p, where
. Based on the irreducibility of some polynomials on
, we focus on characterizing the bent functions for n=p
v
q
r
and n=2p
v
q
r
, where
is an odd prime and p a primitive root modulo q
2. Moreover, the enumerations of those functions are also considered.
Partially supported by the NSF of China under Grants No. 60603012 and No. 60573053. 相似文献
9.
Matching Points with Squares 总被引:1,自引:0,他引:1
Bernardo M. Ábrego Esther M. Arkin Silvia Fernández-Merchant Ferran Hurtado Mikio Kano Joseph S. B. Mitchell Jorge Urrutia 《Discrete and Computational Geometry》2009,41(1):77-95
Given a class
of geometric objects and a point set P, a
-matching of P is a set
of elements of
such that each C
i
contains exactly two elements of P and each element of P lies in at most one C
i
. If all of the elements of P belong to some C
i
, M is called a perfect matching. If, in addition, all of the elements of M are pairwise disjoint, we say that this matching M is strong. In this paper we study the existence and characteristics of
-matchings for point sets in the plane when
is the set of isothetic squares in the plane. A consequence of our results is a proof that the Delaunay triangulations for
the L
∞ metric and the L
1 metric always admit a Hamiltonian path. 相似文献
10.
Mark Pankov 《Journal of Algebraic Combinatorics》2007,26(2):143-159
Let V and V′ be 2n-dimensional vector spaces over fields F and F′. Let also Ω: V× V→ F and Ω′: V′× V′→ F′ be non-degenerate symplectic forms. Denote by Π and Π′ the associated (2n−1)-dimensional projective spaces. The sets of k-dimensional totally isotropic subspaces of Π and Π′ will be denoted by and ${\mathcal G}'_{k}$, respectively. Apartments of the associated buildings intersect and by so-called base subsets. We show that every mapping of to sending base subsets to base subsets is induced by a symplectic embedding of Π to Π′. 相似文献
11.
Sangwook Kim 《Discrete and Computational Geometry》2008,40(2):190-213
We prove that if a simplicial complex Δ is shellable, then the intersection lattice L
Δ for the corresponding diagonal arrangement
is homotopy equivalent to a wedge of spheres. Furthermore, we describe precisely the spheres in the wedge, based on the data
of shelling. Also, we give some examples of diagonal arrangements
where the complement
is K(π,1), coming from rank-3 matroids.
This work forms part of the author’s doctoral dissertation at the University of Minnesota, supervised by Vic Reiner, and partially
supported by NSF grant DMS-0245379. 相似文献
12.
Quillen’s algebraic K-theory is reconstructed via Voevodsky’s algebraic cobordism. More precisely, for a ground field k the algebraic cobordism P1-spectrum MGL of Voevodsky is considered as a commutative P1-ring spectrum. Setting we regard the bigraded theory MGL
p,q
as just a graded theory. There is a unique ring morphism which sends the class [X]MGL of a smooth projective k-variety X to the Euler characteristic of the structure sheaf . Our main result states that there is a canonical grade preserving isomorphism of ring cohomology theories
on the category in the sense of [6], where K*(X
on
Z) is Thomason–Trobaugh K-theory and K′
* is Quillen’s K′-theory. In particular, the left hand side is a ring cohomology theory. Moreover both theories are oriented in the sense of
[6] and ϕ respects the orientations. The result is an algebraic version of a theorem due to Conner and Floyd. That theorem
reconstructs complex K-theory via complex cobordism [1]. 相似文献
13.
A. Krajka 《Acta Appl Math》2007,96(1-3):327-338
Let
be a probability space with a nonatomic measure P and let (S,ρ) be a separable complete metric space. Let {N
n
,n≥1} be an arbitrary sequence of positive-integer valued random variables. Let {F
k
,k≥1} be a family of probability laws and let X be some random element defined on
and taking values in (S,ρ).
In this paper we present necessary and sufficient conditions under which one can construct an array of random elements {X
n,k
,n,k≥1} defined on the same probability space and taking values in (S,ρ), and such that
, and moreover
as n→∞. Furthermore, we consider the speed of convergence
to X as n→∞.
相似文献
14.
Valentina S. Harizanov Carl G. JockuschJr. Julia F. Knight 《Archive for Mathematical Logic》2009,48(1):39-53
We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable
partial ordering which has an infinite chain but none that is or , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering
which has an infinite chain must have an infinite chain that is the difference of two sets. Our main result is that there is a computably axiomatizable theory K of partial orderings such that K has a computable model with arbitrarily long finite chains but no computable model with an infinite chain. We also prove
the corresponding result for antichains. Finally, we prove that if a computable partial ordering has the feature that for every , there is an infinite chain or antichain that is relative to , then we have uniform dichotomy: either for all copies of , there is an infinite chain that is relative to , or for all copies of , there is an infinite antichain that is relative to . 相似文献
15.
16.
Sophie Chemla 《Transformation Groups》2008,13(1):91-123
In this paper, X will denote a manifold. In a very famous paper, Kontsevich [Ko] showed that the differential graded Lie algebra (DGLA) of polydifferential
operators on X is formal. Calaque [C1] extended this theorem to any Lie algebroid. More precisely, given any Lie algebroid E over X, he defined the DGLA of E-polydifferential operators, and showed that it is formal. Denote by the DGLA of E-polyvector fields. Considering M, a module over E, we define the-module of E-polyvector fields with values in M. Similarly, we define the-module of E-polydifferential operators with values in M,. We show that there is a quasi-isomorphism of L
∞-modules over from to . Our result extends Calaque’s (and Kontsevich’s) result. 相似文献
17.
The semantic constructions and results for definite programs do not extend when dealing with negation. The main problem is
related to a well-known problem in the area of algebraic specification: if we fix a constraint domain as a given model, its
free extension by means of a set of Horn clauses defining a set of new predicates is semicomputable. However, if the language
of the extension is richer than Horn clauses its free extension (if it exists) is not necessarily semicomputable. In this
paper we present a framework that allows us to deal with these problems in a novel way. This framework is based on two main
ideas: a reformulation of the notion of constraint domain and a functorial presentation of our semantics. In particular, the
semantics of a logic program P is defined in terms of three functors: that apply to constraint domains and provide the operational, the least fixpoint and the logical semantics of P, respectively. To be more concrete, the idea is that the application of to a specific constraint solver provides the operational semantics of P that uses this solver; the application of to a specific domain provides the least fixpoint of P over this domain; and, the application of to a theory of constraints provides the logic theory associated to P. In this context, we prove that these three functors are in some sense equivalent.
相似文献
18.
Let ℳ be a von Neumann factor of type II1 with a normalized trace τ. In 1983 L. G. Brown showed that to every operator T∈ℳ one can in a natural way associate a spectral distribution measure
μ
T (now called the Brown measure of T), which is a probability measure in ℂ with support in the spectrum σ(T) of T. In this paper it is shown that for every T∈ℳ and every Borel set B in ℂ, there is a unique closed T-invariant subspace
affiliated with ℳ, such that the Brown measure of
is concentrated on B and the Brown measure of
is concentrated on ℂ∖B. Moreover,
is T-hyperinvariant and the trace of
is equal to μ
T(B). In particular, if T∈ℳ has a Brown measure which is not concentrated on a singleton, then there exists a non-trivial, closed,
T-hyperinvariant subspace. Furthermore, it is shown that for every T∈ℳ the limit
exists in the strong operator topology, and the projection onto
is equal to 1[0,r](A), for every r>0.
Supported by The Danish National Research Foundation. 相似文献
19.
In this paper we show that each factorization structure on a small category , satisfying certain conditions, yields a presheaf on and a morphism of presheaves . We then give connections, and set up one to one correspondences, between subclasses of the following classes: (a) closure operators on (b) subobjects of (c) morphisms from to (d) weak Lawvere–Tierney topologies (e) weak Grothendieck topologies (f) closure operators on . 相似文献
20.
Jesús A. Álvarez López Yuri A. Kordyukov 《Journal of Fixed Point Theory and Applications》2008,3(2):273-305
Let be a smooth foliation on a closed Riemannian manifold M, and let Λ be a transverse invariant measure of . Suppose that Λ is absolutely continuous with respect to the Lebesgue measure on smooth transversals. Then a topological
definition of the Λ-Lefschetz number of any leaf preserving diffeomorphism is given. For this purpose, standard results about smooth approximation and transversality are extended to the case of foliation
maps. It is asked whether this topological Λ-Lefschetz number is equal to the analytic Λ-Lefschetz number defined by Heitsch
and Lazarov, which would be a version of the Lefschetz trace formula. Heitsch and Lazarov have shown such a trace formula
when the fixed point set is transverse to .
Dedicated to V. I. Arnold 相似文献