共查询到20条相似文献,搜索用时 15 毫秒
1.
We prove that the red—blue discrepancy of the set system formed by n points and n axis-parallel boxes in <bo>R</bo>
d
can be as high as n
Ω(1)
in any dimension d= Ω(log n) . This contrasts with the fixed-dimensional case d=O(1) , where the discrepancy is always polylogarithmic. More generally we show that in any dimension 1<d= O(log n) the maximum discrepancy is 2
Ω(d)
. Our result also leads to a new lower bound on the complexity of off-line orthogonal range searching. This is the problem
of summing up weights in boxes, given n weighted points and n boxes in <bo>R</bo>
d
. We prove that the number of arithmetic operations is at least Ω(nd+ nlog log n) in any dimension d=O(log n) .
Received June 30, 2000, and in revised form November 9, 2000. Online publication April 6, 2001. 相似文献
2.
We consider in this paper random flights in ℝ
d
performed by a particle changing direction of motion at Poisson times. Directions are uniformly distributed on hyperspheres
S
1
d
. We obtain the conditional characteristic function of the position of the particle after n changes of direction. From this characteristic function we extract the conditional distributions in terms of (n+1)−fold integrals of products of Bessel functions. These integrals can be worked out in simple terms for spaces of dimension
d=2 and d=4. In these two cases also the unconditional distribution is determined in explicit form. Some distributions connected with
random flights in ℝ3 are discussed and in some special cases are analyzed in full detail. We point out that a strict connection between these
types of motions with infinite directions and the equation of damped waves holds only for d=2.
Related motions with random velocity in spaces of lower dimension are analyzed and their distributions derived. 相似文献
3.
Isaac Meilijson 《Israel Journal of Mathematics》1990,72(3):341-352
This paper presents formulas and asymptotic expansions for the expected number of vertices and the expected volume of the
convex hull of a sample ofn points taken from the uniform distribution on ad-dimensional ball. It is shown that the expected number of vertices is asymptotically proportional ton
(d−1)/(d+1), which generalizes Rényi and Sulanke’s asymptotic raten
(1/3) ford=2 and agrees with Raynaud’s asymptotic raten
(d−1)/(d+1) for the expected number of facets, as it should be, by Bárány’s result that the expected number ofs-dimensional faces has order of magnitude independent ofs. Our formulas agree with the ones Efron obtained ford=2 and 3 under more general distributions. An application is given to the estimation of the probability content of an unknown
convex subset ofR
d
. 相似文献
4.
R. A. Dwyer 《Discrete and Computational Geometry》2000,23(3):343-365
This report considers the expected combinatorial complexity of the Euclidean Voronoi diagram and the convex hull of sets
of n independent random points moving in unit time between two positions drawn independently from the same distribution in R
d
for fixed d\ge 2 as n→∈fty . It is proved that, when the source and destination distributions are the uniform distribution on the unit d -ball, these complexities are Θ(n
(d+1)/d
) for the Voronoi diagram and O(n
(d-1)/(d+1)
log n) for the convex hull. Additional results for the convex hull are O( log
d
n) for the uniform distribution in the unit d -cube and O( log
(d+1)/2
n) for the d -dimensional normal distribution.
Received November 23, 1998, and in revised form July 8, 1999. 相似文献
5.
《Journal of computational and graphical statistics》2013,22(2):352-362
This article considers computational aspects of the nonparametric maximum likelihood estimator (NPMLE) for the distribution function of bivariate interval-censored data. The computation of the NPMLE consists of a parameter reduction step and an optimization step. This article focuses on the reduction step and introduces two new reduction algorithms: the Tree algorithm and the HeightMap algorithm. The Tree algorithm is mentioned only briefly. The HeightMap algorithm is discussed in detail and also given in pseudo code. It is a fast and simple algorithm of time complexityO(n2). This is an order faster than the best known algorithm thus far by Bogaerts and Lesaffre. We compare the new algorithms to earlier algorithms in a simulation study, and demonstrate that the new algorithms are significantly faster. Finally, we discuss how the HeightMap algorithm can be generalized to d-dimensional data with d > 2. Such a multivariate version of the HeightMap algorithm has time complexity O(nd). 相似文献
6.
Colin Cooper 《Random Structures and Algorithms》2004,25(4):353-375
We study random r‐uniform n vertex hypergraphs with fixed degree sequence d = (d1…,dn), maximum degree Δ = o(n1/24) and total degree θn, where θ is bounded. We give the size, number of edges and degree sequence of the κ ≥ 2) up to a whp error of O(n2/3 Δ4/3 log n). In the case of graphs (r = 2) we give further structural details such as the number of tree components and, for the case of smooth degree sequences, the size of the mantle. We give various examples, such as the cores of r‐uniform hypergraphs with a near Poisson degree sequence, and an improved upper bound for the first linear dependence among the columns in the independent column model of random Boolean matrices. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 25, 2004 相似文献
7.
Ahmed Abouelaz Enrico Casadio Tarabusi Abdallah Ihsane 《Mediterranean Journal of Mathematics》2009,6(3):303-316
We study the Radon transform R on the discrete Grassmannian of rank-d affine sublattices of Z
n
for 0 < d < n, extending and building on previous work of the first- and third-named authors in codimension 1. By analogy with the integral
geometry on Grassmannians in R
n
, various natural questions are treated, such as definition and properties of R and its dual transform R
*, function space setting, support theorems and inversion formulas. 相似文献
8.
The aim of the present paper is to characterize prime numbers of the form n = x
2 + (x + 1)2 and to obtain certain proper divisors of composite numbers of the same form, i.e. divisors d of n such that 1 < d < n.
相似文献
9.
Mine aglar 《商业与工业应用随机模型》2000,16(1):23-33
The maximum likelihood estimator for the drift of a Brownian flow on ℝd, d ⩾ 2, is found with the assumption that the covariance is known. By approximation of the drift with known functions, the statistical model is reduced to a parametric one that is a curved exponential family. The data is the n‐point motion of the Brownian flow throughout the time interval [0, T]. The asymptotic properties of the MLE are also investigated. Copyright © 2000 John Wiley & Sons, Ltd. 相似文献
10.
The problem of triangulating a polygon using the minimum number of triangles is treated. We show that the minimum number of triangles required to partition a simplen-gon is equal ton+2w –d – 2, wherew is the number of holes andd is the maximum number of independent degenerate triangles of then-gon. We also propose an algorithm for constructing the minimum triangulation of a simple hole-freen-gon. The algorithm takesO(nlog2
n+DK
2) time, whereD is the maximum number of vertices lying on the same line in then-gon andK is the number of minimally degenerate triangles of then-gon. 相似文献
11.
We prove d-linear analogues of the classical restriction and Kakeya conjectures in R
d
. Our approach involves obtaining monotonicity formulae pertaining to a certain evolution of families of gaussians, closely
related to heat flow. We conclude by giving some applications to the corresponding variable-coefficient problems and the so-called
“joints” problem, as well as presenting some n-linear analogues for n < d. 相似文献
12.
Hanno Lefmann 《Discrete and Computational Geometry》2008,40(3):401-413
We consider a variant of Heilbronn’s triangle problem by investigating for a fixed dimension d≥2 and for integers k≥2 with k≤d distributions of n points in the d-dimensional unit cube [0,1]
d
, such that the minimum volume of the simplices, which are determined by (k+1) of these n points is as large as possible. Denoting by Δ
k,d
(n), the supremum of this minimum volume over all distributions of n points in [0,1]
d
, we show that c
k,d
⋅(log n)1/(d−k+1)/n
k/(d−k+1)≤Δ
k,d
(n)≤c
k,d
′/n
k/d
for fixed 2≤k≤d, and, moreover, for odd integers k≥1, we show the upper bound Δ
k,d
(n)≤c
k,d
″/n
k/d+(k−1)/(2d(d−1)), where c
k,d
,c
k,d
′,c
k,d
″>0 are constants.
A preliminary version of this paper appeared in COCOON ’05. 相似文献
13.
Jan-Christoph Schlage-Puchta 《Israel Journal of Mathematics》2010,177(1):229-251
For a finitely generated group Γ denote by μ(Γ) the growth coefficient of Γ, that is, the infimum over all real numbers d such that s
n
(Γ) < n!
d
. We show that the growth coefficient of a virtually free group is always rational, and that every rational number occurs
as growth coefficient of some virtually free group. 相似文献
14.
Chen Jiecheng Zhu Xiangrong 《高校应用数学学报(英文版)》2005,20(3):316-322
Given a positive Radon measure μ on R^d satisfying the linear growth condition μ(B(x,r))≤C0r^n,x∈R^d,r〉0,(1) where n is a fixed number and O〈n≤d. When d-1〈n,it is proved that if Tt,N1=0,then the corresponding maximal Calderon-Zygmund singular integral is bounded from RBMO to itself only except that it is infinite μ-a. e. on R^d. 相似文献
15.
Hans TRIEBEL 《数学学报(英文版)》2008,24(4):539-554
A space Apq^s (R^n) with A : B or A = F and s ∈R, 0 〈 p, q 〈 ∞ either has a trace in Lp(Г), where Г is a compact d-set in R^n with 0 〈 d 〈 n, or D(R^n/Г) is dense in it. Related dichotomy numbers are introduced and calculated. 相似文献
16.
We present a new (1+ε)-spanner for sets of n points in ℝ
d
. Our spanner has size O(n/ε
d−1) and maximum degree O(log
d
n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming that the trajectories
of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n
2/ε
d−1), and using a supporting data structure of size O(nlog
d
n), we can handle events in time O(log
d+1
n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in ℝ
d
whose performance does not depend on the spread of the point set. 相似文献
17.
Masafumi Akahira 《Annals of the Institute of Statistical Mathematics》1987,39(1):25-36
Summary The problem to estimate a common parameter for the pooled sample from the double exponential distributions is discussed in
the presence of nuisance parameters. The maximum likelihood estimator, a weighted median, a weighted mean and others are asymptotically
compared up to the second order, i.e. the ordern
−1/2 with the asymptotic expansions of their distributions.
University of Electro-communications 相似文献
18.
Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple
algorithm introduced by Steger and Wormald [10] and prove that it produces an asymptotically uniform random regular graph
in a polynomial time. Precisely, for fixed d and n with d = O(n1/3−ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd2). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality
by the second author.
The algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs.
* Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship. 相似文献
19.
For given integers d,j≥2 and any positive integers n, distributions of n points in the d-dimensional unit cube [0,1]d are investigated, where the minimum volume of the convex hull determined by j of these n points is large. In particular, for fixed integers d,k≥2 the existence of a configuration of n points in [0,1]d is shown, such that, simultaneously for j=2,…,k, the volume of the convex hull of any j points among these n points is Ω(1/n(j−1)/(1+|d−j+1|)). Moreover, a deterministic algorithm is given achieving this lower bound, provided that d+1≤j≤k. 相似文献
20.
M. Sharir 《Discrete and Computational Geometry》1994,12(1):327-345
We consider the problem of bounding the combinatorial complexity of the lower envelope ofn surfaces or surface patches ind-space (d≥3), all algebraic of constant degree, and bounded by algebraic surfaces of constant degree. We show that the complexity of
the lower envelope ofn such surface patches isO(n
d−1+∈), for any ∈>0; the constant of proportionality depends on ∈, ond, ons, the maximum number of intersections among anyd-tuple of the given surfaces, and on the shape and degree of the surface patches and of their boundaries. This is the first
nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity
of the envelope isO(n
d-2λ
q
(n)) for some constantq depending on the shape and degree of the surfaces (where λ
q
(n) is the maximum length of (n, q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with
expected running timeO(n
2+∈), and give several applications of the new bounds.
Work on this paper has been supported by NSF Grant CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation,
the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered
by the Israeli Academy of Sciences. 相似文献