共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
Given a metric M=(V,d), a graph G=(V,E) is a t-spanner for M if every pair of nodes in V has a “short” path (i.e., of length at most t times their actual distance) between them in the spanner. Furthermore, this spanner has a hop diameter bounded by D if every pair of nodes has such a short path that also uses at most D edges. We consider the problem of constructing sparse (1+ε)-spanners with small hop diameter for metrics of low doubling dimension.
In this paper, we show that given any metric with constant doubling dimension k and any 0<ε<1, one can find (1+ε)-spanner for the metric with nearly linear number of edges (i.e., only O(nlog *
n+n
ε
−O(k)) edges) and constant hop diameter; we can also obtain a (1+ε)-spanner with linear number of edges (i.e., only n
ε
−O(k) edges) that achieves a hop diameter that grows like the functional inverse of Ackermann’s function. Moreover, we prove that
such tradeoffs between the number of edges and the hop diameter are asymptotically optimal.
The conference version of the paper appeared in ACM-SIAM SODA 2006.
This research of T.-H.H. Chan was done while the author was at Carnegie Mellon University and was partly supported by the
NSF grant CCR-0122581 (the ALADDIN project), the NSF CAREER award CCF-0448095, and by an Alfred P. Sloan Fellowship.
This research of A. Gupta was partly supported by the NSF grant CCR-0122581 (the ALADDIN project), the NSF CAREER award CCF-0448095,
and by an Alfred P. Sloan Fellowship. 相似文献
3.
Larry Guth 《Geometric And Functional Analysis》2007,17(4):1139-1179
We prove that a bounded open set U in has k-width less than C(n) Volume(U)
k/n
. Using this estimate, we give lower bounds for the k-dilation of degree 1 maps between certain domains in . In particular, we estimate the smallest (n – 1)-dilation of any degree 1 map between two n-dimensional rectangles. For any pair of rectangles, our estimate is accurate up to a dimensional constant C(n). We give examples in which the (n – 1)-dilation of the linear map is bigger than the optimal value by an arbitrarily large factor.
Received: January 2006, Revision: May 2006, Accepted: June 2006 相似文献
4.
We present an optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source
s on the surface of a convex polytope P in three dimensions. Our algorithm runs in O(nlog n) time and requires O(nlog n) space, where n is the number of edges of P. The algorithm is based on the O(nlog n) algorithm of Hershberger and Suri for shortest paths in the plane (Hershberger, J., Suri, S. in SIAM J. Comput. 28(6):2215–2256,
1999), and similarly follows the continuous Dijkstra paradigm, which propagates a “wavefront” from s along ∂
P. This is effected by generalizing the concept of conforming subdivision of the free space introduced by Hershberger and Suri
and by adapting it for the case of a convex polytope in ℝ3, allowing the algorithm to accomplish the propagation in discrete steps, between the “transparent” edges of the subdivision.
The algorithm constructs a dynamic version of Mount’s data structure (Mount, D.M. in Discrete Comput. Geom. 2:153–174, 1987) that implicitly encodes the shortest paths from s to all other points of the surface. This structure allows us to answer single-source shortest-path queries, where the length
of the path, as well as its combinatorial type, can be reported in O(log n) time; the actual path can be reported in additional O(k) time, where k is the number of polytope edges crossed by the path.
The algorithm generalizes to the case of m source points to yield an implicit representation of the geodesic Voronoi diagram of m sites on the surface of P, in time O((n+m)log (n+m)), so that the site closest to a query point can be reported in time O(log (n+m)).
Work on this paper was supported by NSF Grants CCR-00-98246 and CCF-05-14079, by a grant from the U.S.-Israeli Binational
Science Foundation, by grant 155/05 from the Israel Science Fund, and by the Hermann Minkowski–MINERVA Center for Geometry
at Tel Aviv University. The paper is based on the Ph.D. Thesis of the first author, supervised by the second author. A preliminary
version has been presented in Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 30–39, 2006. 相似文献
5.
The Fast Johnson–Lindenstrauss Transform (FJLT) was recently discovered by Ailon and Chazelle as a novel technique for performing
fast dimension reduction with small distortion from ℓ
2
d
to ℓ
2
k
in time O(max {dlog d,k
3}). For k in [Ω(log d),O(d
1/2)], this beats time O(dk) achieved by naive multiplication by random dense matrices, an approach followed by several authors as a variant of the seminal
result by Johnson and Lindenstrauss (JL) from the mid 1980s. In this work we show how to significantly improve the running
time to O(dlog k) for k=O(d
1/2−δ
), for any arbitrary small fixed δ. This beats the better of FJLT and JL. Our analysis uses a powerful measure concentration bound due to Talagrand applied
to Rademacher series in Banach spaces (sums of vectors in Banach spaces with random signs). The set of vectors used is a real
embedding of dual BCH code vectors over GF(2). We also discuss the number of random bits used and reduction to ℓ
1 space.
The connection between geometry and discrete coding theory discussed here is interesting in its own right and may be useful
in other algorithmic applications as well. 相似文献
6.
Wei-jie Cong Hong-wei Liu Feng Ye Shui-sheng Zhou 《Computational Optimization and Applications》2012,51(1):241-257
We consider the problem of computing a (1+ε)-approximation to the minimum volume enclosing ellipsoid (MVEE) of a given set of m points in R
n
. Based on the idea of sequential minimal optimization (SMO) method, we develop a rank-two update algorithm. This algorithm
computes an approximate solution to the dual optimization formulation of the MVEE problem, which updates only two weights
of the dual variable at each iteration. We establish that this algorithm computes a (1+ε)-approximation to MVEE in O(mn
3/ε) operations and returns a core set of size O(n
2/ε) for ε∈(0,1). In addition, we give an extension of this rank-two update algorithm. Computational experiments show the proposed algorithms
are very efficient for solving large-scale problem with a high accuracy. 相似文献
7.
An essential cycle on a surface is a simple cycle that cannot be continuously deformed to a point or a single boundary. We
describe algorithms to compute the shortest essential cycle in an orientable combinatorial surface in O(n
2log n) time, or in O(nlog n) time when both the genus and number of boundaries are fixed. Our results correct an error in a paper of Erickson and Har-Peled
(Discrete Comput. Geom. 31(1):37–59, 2004). 相似文献
8.
Yevgeny Schreiber 《Discrete and Computational Geometry》2010,43(1):21-53
We generalize our optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed
source s on the surface of a convex polytope P to three realistic scenarios where P is a possibly nonconvex polyhedron. In the first scenario, ∂
P is a terrain whose maximum facet slope is bounded by any fixed constant. In the second scenario, P is an uncrowded polyhedron—each axis-parallel square h of side length l(h) whose smallest Euclidean distance to a vertex of P is at least l(h) is intersected by at most O(1) facets of ∂
P—an input model which, as we show, is a generalization of the well-known low-density model. In the third scenario, P is self-conforming—here, for each edge e of P, there is a connected region R(e) of O(1) facets whose union contains e, so that the shortest path distance from e to any edge e′ of ∂
R(e) is at least c⋅max {|e|,|e′|}, where c is some positive constant. In particular, it includes the case where each facet of ∂
P is fat and each vertex is incident to at most O(1) facets of ∂
P. In all the above cases the algorithm runs in O(nlog n) time and space, where n is the number of edges of P, and produces an implicit representation of the shortest-path map, so that the shortest path from s to any query point q can be determined in O(log n) time. The constants of proportionality depend on the various parameters (maximum facet slope, crowdedness, etc.). We also
note that the self-conforming model allows for a major simplification of the algorithm. 相似文献
9.
We present some exponential inequalities for positively associated unbounded random variables. By these inequalities, we obtain
the rate of convergence n
−1/2
β
n
log 3/2
n in which β
n
can be particularly taken as (log log n)1/σ
with any σ>2 for the case of geometrically decreasing covariances, which is faster than the corresponding one n
−1/2(log log n)1/2log 2
n obtained by Xing, Yang, and Liu in J. Inequal. Appl., doi: (2008) for the case mentioned above, and derive the convergence rate n
−1/2
β
n
log 1/2
n for the above β
n
under the given covariance function, which improves the relevant one n
−1/2(log log n)1/2log n obtained by Yang and Chen in Sci. China, Ser. A 49(1), 78–85 (2006) for associated uniformly bounded random variables. In addition, some moment inequalities are given to prove the main results,
which extend and improve some known results. 相似文献
10.
Boris N. Khoromskij 《Constructive Approximation》2011,34(2):257-280
In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high-dimensional
applications. We describe the multifolding or quantics-based tensor approximation method of O(dlog N)-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set {1,…,N}⊗d
, or briefly N-d tensors of size N
d
, and to the respective discretized differential-integral operators in ℝ
d
. As the basic approximation result, we prove that a complex exponential sampled on an equispaced grid has quantics rank 1.
Moreover, a Chebyshev polynomial, sampled over a Chebyshev Gauss–Lobatto grid, has separation rank 2 in the quantics tensor
format, while for the polynomial of degree m over a Chebyshev grid the respective quantics rank is at most 2m+1. For N-d tensors generated by certain analytic functions, we give a constructive proof of the O(dlog Nlog ε
−1)-complexity bound for their approximation by low-rank 2-(dlog N) quantics tensors up to the accuracy ε>0. In the case ε=O(N
−α
), α>0, our approach leads to the quantics tensor numerical method in dimension d, with the nearly optimal asymptotic complexity O(d/αlog 2
ε
−1). From numerical examples presented here, we observe that the quantics tensor method has proved its value in application
to various function related tensors/matrices arising in computational quantum chemistry and in the traditional finite element
method/boundary element method (FEM/BEM). The tool apparently works. 相似文献
11.
Sunil Arya Theocharis Malamatos David M. Mount 《Discrete and Computational Geometry》2009,41(3):398-443
Given an n-element point set in ℝ
d
, the range searching problem involves preprocessing these points so that the total weight, or for our purposes the semigroup
sum, of the points lying within a given query range η can be determined quickly. In ε-approximate range searching we assume that η is bounded, and the sum is required to include all the points that lie within η and may additionally include any of the points lying within distance ε⋅diam(η) of η’s boundary.
In this paper we contrast the complexity of approximate range searching based on properties of the semigroup and range space.
A semigroup (S,+) is idempotent if x+x=x for all x∈S, and it is integral if for all k≥2, the k-fold sum x+⋅⋅⋅+x is not equal to x. Recent research has shown that the computational complexity of approximate spherical range searching is significantly lower
for idempotent semigroups than it is for integral semigroups in terms of the dependencies on ε. In this paper we consider whether these results can be generalized to other sorts of ranges. We show that, as with integrality,
allowing sharp corners on ranges has an adverse effect on the complexity of the problem. In particular, we establish lower
bounds on the worst-case complexity of approximate range searching in the semigroup arithmetic model for ranges consisting
of d-dimensional unit hypercubes under rigid motions. We show that for arbitrary (including idempotent) semigroups and linear
space, the query time is at least
. In the case of integral semigroups we prove a tighter lower bound of Ω(1/ε
d−2). These lower bounds nearly match existing upper bounds for arbitrary semigroups.
In contrast, we show that the improvements offered by idempotence do apply to smooth convex ranges. We say that a range is
smooth if at every boundary point there is an incident Euclidean sphere that lies entirely within the range whose radius is proportional
to the range’s diameter. We show that for smooth ranges and idempotent semigroups, ε-approximate range queries can be answered in O(log n+(1/ε)(d−1)/2log (1/ε)) time using O(n/ε) space. We show that this is nearly tight by presenting a lower bound of Ω(log n+(1/ε)(d−1)/2). This bound is in the decision-tree model and holds irrespective of space.
A preliminary version of this paper appeared in the Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 11–20, 2006.
The research of S. Arya was supported by the Research Grants Council, Hong Kong, China under project number HKUST6184/04E.
The research of D.M. Mount was partially supported by the National Science Foundation under grant CCR-0635099 and the Office
of Naval Research under grant N00014-08-1-1015. 相似文献
12.
Jie Gao Michael Langberg Leonard J. Schulman 《Discrete and Computational Geometry》2008,40(4):537-560
The analysis of incomplete data is a long-standing challenge in practical statistics. When, as is typical, data objects are
represented by points in ℝ
d
, incomplete data objects correspond to affine subspaces (lines or Δ-flats). With this motivation we study the problem of finding the minimum intersection radius
r(ℒ) of a set of lines or Δ-flats ℒ: the least r such that there is a ball of radius r intersecting every flat in ℒ. Known algorithms for finding the minimum enclosing ball for a point set (or clustering by several
balls) do not easily extend to higher-dimensional flats, primarily because “distances” between flats do not satisfy the triangle
inequality. In this paper we show how to restore geometry (i.e., a substitute for the triangle inequality) to the problem,
through a new analog of Helly’s theorem. This “intrinsic-dimension” Helly theorem states: for any family ℒ of Δ-dimensional convex sets in a Hilbert space, there exist Δ+2 sets ℒ′⊆ℒ such that r(ℒ)≤2r(ℒ′). Based upon this we present an algorithm that computes a (1+ε)-core set ℒ′⊆ℒ, |ℒ′|=O(Δ
4/ε), such that the ball centered at a point c with radius (1+ε)r(ℒ′) intersects every element of ℒ. The running time of the algorithm is O(n
Δ+1
dpoly (Δ/ε)). For the case of lines or line segments (Δ=1), the (expected) running time of the algorithm can be improved to O(ndpoly (1/ε)). We note that the size of the core set depends only on the dimension of the input objects and is independent of the input
size n and the dimension d of the ambient space.
An extended abstract appeared in ACM–SIAM Symposium on Discrete Algorithms, 2006.
Work was done when J. Gao was with Center for the Mathematics of Information, California Institute of Technology.
Work was done when M. Langberg was a postdoctoral scholar at the California Institute of Technology. Research supported in
part by NSF grant CCF-0346991.
Research of L.J. Schulman supported in part by an NSF ITR and the Okawa Foundation. 相似文献
13.
Y. Lacroix 《Israel Journal of Mathematics》2002,132(1):253-263
LetG denote the set of decreasingG: ℝ→ℝ withGэ1 on ]−∞,0], and ƒ
0
∞
G(t)dt⩽1. LetX be a compact metric space, andT: X→X a continuous map. Let μ denone aT-invariant ergodic probability measure onX, and assume (X, T, μ) to be aperiodic. LetU⊂X be such that μ(U)>0. Let τ
U
(x)=inf{k⩾1:T
k
xεU}, and defineG
U
(t)=1/u(U)u({xεU:u(U)τU(x)>t),tεℝ We prove that for μ-a.e.x∈X, there exists a sequence (U
n
)
n≥1
of neighbourhoods ofx such that {x}=∩
n
U
n
, and for anyG ∈G, there exists a subsequence (n
k
)
k≥1
withG
U
n
k
↑U weakly.
We also construct a uniquely ergodic Toeplitz flowO(x
∞,S, μ), the orbit closure of a Toeplitz sequencex
∞, such that the above conclusion still holds, with moreover the requirement that eachU
n
be a cylinder set.
In memory of Anzelm Iwanik 相似文献
14.
The Integer Knapsack Problem with Set-up Weights (IKPSW) is a generalization of the classical Integer Knapsack Problem (IKP),
where each item type has a set-up weight that is added to the knapsack if any copies of the item type are in the knapsack
solution. The k-item IKPSW (kIKPSW) is also considered, where a cardinality constraint imposes a value k on the total number of items in the knapsack solution. IKPSW and kIKPSW have applications in the area of aviation security. This paper provides dynamic programming algorithms for each problem
that produce optimal solutions in pseudo-polynomial time. Moreover, four heuristics are presented that provide approximate
solutions to IKPSW and kIKPSW. For each problem, a Greedy heuristic is presented that produces solutions within a factor of 1/2 of the optimal solution
value, and a fully polynomial time approximation scheme (FPTAS) is presented that produces solutions within a factor of ε of the optimal solution value. The FPTAS for IKPSW has time and space requirements of O(nlog n+n/ε
2+1/ε
3) and O(1/ε
2), respectively, and the FPTAS for kIKPSW has time and space requirements of O(kn
2/ε
3) and O(k/ε
2), respectively. 相似文献
15.
We consider Las Vegas randomized dynamic algorithms for on-line connectivity problems with deletions only. In particular, we show that starting from a graph with m edges and n nodes, we can maintain a spanning forest during m deletions in O(m log(n2/m) + n(log n)3(log log n)2) expected time, which is O(m) if m = Θ(n2) and O(m log n) if m = Ω(n(log n log log n)2). The deletions may be interspersed with connectivity queries, each of which is answered in constant time. The previous best bound was O(m log2 n) by Henzinger and Thorup which covered both insertions and deletions. The result is based on a general randomized reduction for edge connectivity problems of many deletions-only queries to a few deletions and insertions queries. For 2-edge connectivity, the complexity is improved from O(m(log n)5) to O(m log(n2/m) + n(log n)6(log log n)2). For the general decremental k-edge-connectivity problem, we get a total running time of O(k2n2 polylog n). Here the previous best bound was O(kmn polylog n). Improved running times are also achieved for the static consensus tree problem, with applications to computational biology and relational data bases. 相似文献
16.
A. G. Baskakov 《Mathematical Notes》2000,67(6):690-698
We obtain conditions for the invertibility and the Fredholm property of the difference operator (Dx)(n)=x(n) -U(n)x(n − 1),n ε ℤ, in the Banach space l
p
(ℤ, X),p ε [1, ∞], of vector sequences, whereX is a Banach space andU is a bounded operator function.
Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 816–827, June, 2000. 相似文献
17.
We define an invariant of measure-theoretic isomorphism for dynamical systems, as the growth rate inn of the number of small
-balls aroundα-n-names necessary to cover most of the system, for any generating partitionα. We show that this rate is essentially bounded if and only if the system is a translation of a compact group, and compute
it for several classes of systems of entropy zero, thus getting examples of growth rates inO(n),O(n
k
) fork ε ℕ, oro(f(n)) for any given unboundedf, and of various relationships with the usual notion of language complexity of the underlying topological system. 相似文献
18.
We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(knε) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and ε > 0 is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(nε). 相似文献
19.
Let k be an algebraically closed field. Let Λ be the path algebra over k of the linearly oriented quiver
\mathbb An\mathbb A_n for n ≥ 3. For r ≥ 2 and n > r we consider the finite dimensional k −algebra Λ(n,r) which is defined as the quotient algebra of Λ by the two sided ideal generated by all paths of length r. We will determine for which pairs (n,r) the algebra Λ(n,r) is piecewise hereditary, so the bounded derived category D
b
(Λ(n,r)) is equivalent to the bounded derived category of a hereditary abelian category H\mathcal H as triangulated category. 相似文献
20.
We define the index of composition λ(n) of an integer n ⩾ 2 as λ(n) = log n/log γ(n), where γ(n) stands for the product of the primes dividing n, and first establish that λ and 1/λ both have asymptotic mean value 1. We then establish that, given any ɛ > 0 and any integer
k ⩾ 2, there exist infinitely many positive integers n such that . Considering the distribution function F(z,x) := #{n < x : λ(n) > z}, we prove that, given 1 < z < 2 and ɛ > 0, then, if x is sufficiently large,
this last inequality also holding if z ⩾ 2. We then use these inequalities to obtain probabilistic results and we state a conjecture. Finally, using (*), we show
that the probability that the abc conjecture does not hold is 0. 相似文献