共查询到20条相似文献,搜索用时 35 毫秒
1.
Jeff Erickson 《Discrete and Computational Geometry》2005,33(1):83-115
The spread of a finite set of points is the ratio between the
longest and shortest pairwise distances. We prove that the Delaunay
triangulation of any set of $n$ points in~$\Real^3$ with spread
$\Delta$ has complexity $O(\Delta^3)$. This bound is tight in the
worst case for all $\Delta = O(\sqrt{n})$. In particular, the
Delaunay triangulation of any dense point set has linear complexity.
We also generalize this upper bound to regular triangulations of
$k$-ply systems of balls, unions of several dense point sets, and
uniform samples of smooth surfaces. On the other hand, for any $n$
and $\Delta = O(n)$, we construct a regular triangulation of
complexity $\Omega(n\Delta)$ whose $n$ vertices have spread $\Delta$. 相似文献
2.
Stabbing Delaunay Tetrahedralizations 总被引:1,自引:0,他引:1
A Delaunay tetrahedralization of $n$ vertices is exhibited for which
a straight line can pass through the interiors of
$\Theta(n^2)$ tetrahedra.
This solves an open problem of Amenta,
who asked whether a line can stab more than $O(n)$ tetrahedra.
The construction generalizes to higher dimensions: in $d$ dimensions,
a line can stab the interiors of $\Theta(n^{\lceil d / 2 \rceil})$
Delaunay $d$-simplices.
The relationship between a Delaunay triangulation and
a convex polytope yields another result:
a two-dimensional slice of a $d$-dimensional $n$-vertex polytope
can have $\Theta(n^{\lfloor d / 2 \rfloor})$ facets.
This last result was first demonstrated by Amenta and Ziegler,
but the construction given here is simpler and more intuitive. 相似文献
3.
Nina Amenta Dominique Attali Olivier Devillers 《Discrete and Computational Geometry》2012,48(1):19-38
We show that the Delaunay triangulation of a set of n points distributed nearly uniformly on a p-dimensional polyhedron (not necessarily convex) in d-dimensional Euclidean space is $O(n^{\frac{d-k+1}{p}})$ , where $k = \lceil\frac{d+1}{p+1} \rceil$ . This bound is tight in the worst case and improves on the prior upper bound for most values of?p. 相似文献
4.
Given a nonconvex simple polygon $P$ with $n$ vertices, is it possible to construct a data structure which after preprocessing can answer halfspace area queries (i.e., given a line, determine the area of the portion of the polygon above the line) in $o(n)$ time? We answer negatively, proving an $\Omega(n)$ lower bound on the query time of any data structure performing this task. We then consider the offline version of the same problem: given a polygon $P$ with $n$ vertices, and $k$ query lines, we present an algorithm that computes the area of $P$ on both sides of each line in $O(k^{2/3}n^{2/3+\varepsilon}+(n+k)\polylog{n})$ time. Variants of this method allow the query of a collection of weighted polygons with or without holes, and solve several other related problems within the same time bounds. 相似文献
5.
We show that the combinatorial complexity of a single cell in an arrangement of k convex polyhedra in 3-space having n facets
in total is
, for any
, thus settling a conjecture of Aronov et al. We then extend our analysis and show that the overall complexity of the zone
of a low-degree
algebraic surface, or of the boundary of an arbitrary convex set, in an arrangement of k convex polyhedra in 3-space with
n facets in total, is also
, for any
. Finally, we present a deterministic algorithm that constructs a single cell in an arrangement of this kind, in time
, for any
. 相似文献
6.
A triangulation of a set S of points in the plane is a subdivision of the convex hull of S into triangles whose vertices are
points of S. Given a set S of n points in
each moving independently, we wish to maintain a triangulation of S. The triangulation needs to be updated periodically as
the points in S move, so the goal is to maintain a triangulation with a small number of topological events, each being the
insertion or deletion of an edge. We propose a kinetic data structure (KDS) that processes
topological events with high probability if the trajectories of input points are algebraic curves of fixed degree. Each topological
event can be processed in
time. This is the first known KDS for maintaining a triangulation that processes a near-quadratic number of topological events,
and almost matches the
lower bound [1]. The number of topological events can be reduced to
if only k of the points are moving. 相似文献
7.
The interior Dirichlet problem for Laplace's equation on a plane polygonal region $\Omega$ with boundary $\Gamma$ may be reformulated as a second kind integral equation on $\Gamma$. This equation may be solved by the Nyström method using the composite trapezoidal rule. It is known that if the mesh has $O(n)$ points and is graded appropriately, then $O(1/n^2)$ convergence is obtained for the solution of the integral equation and the associated solution to the Dirichlet problem at any $x\in \Omega$. We present a simple extrapolation scheme which increases these rates of convergence to $O(1/n^4)$ . 相似文献
8.
Piotr Gajda Youming Li Leszek Plaskota Grzegorz W. Wasilkowski. 《Mathematics of Computation》2004,73(246):813-825
We present and analyze a new randomized algorithm for numerical computation of weighted integrals over the unbounded domain . The algorithm and its desirable theoretical properties are derived based on certain stochastic assumptions about the integrands. It is easy to implement, enjoys convergence rate, and uses only standard random number generators. Numerical results are also included.
9.
Hendrik Hubrechts 《Foundations of Computational Mathematics》2008,8(1):137-169
Let E
Γ be a family of hyperelliptic curves defined by
, where
is defined over a small finite field of odd characteristic. Then with
in an extension degree n field over this small field, we present a deterministic algorithm for computing the zeta function of the curve
by using Dwork deformation in rigid cohomology. The time complexity of the algorithm is
and it needs
bits of memory. A slight adaptation requires only
space, but costs time
. An implementation of this last result turns out to be quite efficient for n big enough.
H. Hubrechts is a Research Assistant of the Research Foundation–Flanders (FWO–Vlaanderen). 相似文献
10.
Sheng Zhang 《计算数学(英文版)》1994,12(2):113-117
A preconditioning method for the finite element stiffness matrix is given in this paper. The triangulation is refined in a subregion; the preconditioning process is composed of resolution of two regular subproblems; the condition number of the preconditioned matrix is O(1 logH/h), where H and h are mesh sizes of the unrefined and local refined triangulations respectively. 相似文献
11.
Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications, such as simplification of social networks, least squares problems, and numerical solution of symmetric positive definite linear systems. In this paper, inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit (OMP), we introduce a deterministic, greedy edge selection algorithm, which is called the universal greedy approach (UGA) for the graph sparsification problem. For a general spectral sparsification problem, e.g., the positive subset selection problem from a set of $m$ vectors in $\mathbb{R}^n$, we propose a nonnegative UGA algorithm which needs $O(mn^2+ n^3/\epsilon^2)$ time to find a $\frac{1+\epsilon/\beta}{1-\epsilon/\beta}$-spectral sparsifier with positive coefficients with sparsity at most $\lceil\frac{n}{\epsilon^2}\rceil$, where $\beta$ is the ratio between the smallest length and largest length of the vectors. The convergence of the nonnegative UGA algorithm is established. For the graph sparsification problem, another UGA algorithm is proposed which can output a $\frac{1+O(\epsilon)}{1-O(\epsilon)}$-spectral sparsifier with $\lceil\frac{n}{\epsilon^2}\rceil$ edges in $O(m+n^2/\epsilon^2)$ time from a graph with $m$ edges and $n$ vertices under some mild assumptions. This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for. The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear, i.e. $O(m^{1+o(1)})$ for some $o(1)=O(\frac{(\log\log(m))^{2/3}}{\log^{1/3}(m)})$. Finally, extensive experimental results, including applications to graph clustering and least squares regression, show the effectiveness of proposed approaches. 相似文献
12.
Let $P$ be a set of $n$ points in $\Re^d$. The {\em
radius} of a $k$-dimensional flat ${\cal F}$ with
respect to $P$, which we denote by ${\cal RD}({\cal F},P)$,
is defined to be $\max_{p \in P} \mathop{\rm dist}({\cal F},p)$, where
$\mathop{\rm dist}({\cal F},p)$ denotes the Euclidean distance between
$p$ and its projection onto ${\cal F}$. The $k$-flat
radius of $P$, which we denote by ${R^{\rm opt}_k}(P)$, is the
minimum, over all $k$-dimensional flats ${\cal F}$, of
${\cal RD}({\cal F},P)$. We consider the problem of
computing ${R^{\rm opt}_k}(P)$ for a given set of points $P$. We
are interested in the high-dimensional case where $d$ is
a part of the input and not a constant. This problem is
NP-hard even for $k = 1$. We present an algorithm that,
given $P$ and a parameter $0 < \eps \leq 1$, returns a
$k$-flat ${\cal F}$ such that ${\cal RD}({\cal F},P) \leq (1 +
\eps) {R^{\rm opt}_k}(P)$. The algorithm runs in $O(nd
C_{\eps,k})$ time, where $C_{\eps,k}$ is a constant that
depends only on $\eps$ and $k$. Thus the algorithm runs
in time linear in the size of the point set and is a
substantial improvement over previous known algorithms,
whose running time is of the order of $d
n^{O(k/\eps^c)}$, where $c$ is an appropriate constant. 相似文献
13.
The authors present an algorithm which is a modification of the Nguyen-Stehle greedy reduction algorithm due to Nguyen and
Stehle in 2009. This algorithm can be used to compute the Minkowski reduced lattice bases for arbitrary rank lattices with
quadratic bit complexity on the size of the input vectors. The total bit complexity of the algorithm is $O(n^2 \cdot (4n!)^n \cdot (\tfrac{{n!}}
{{2^n }})^{\tfrac{n}
{2}} \cdot (\tfrac{4}
{3})^{\tfrac{{n(n - 1)}}
{4}} \cdot (\tfrac{3}
{2})^{\tfrac{{n^2 (n - 1)}}
{2}} \cdot \log ^2 A)
$O(n^2 \cdot (4n!)^n \cdot (\tfrac{{n!}}
{{2^n }})^{\tfrac{n}
{2}} \cdot (\tfrac{4}
{3})^{\tfrac{{n(n - 1)}}
{4}} \cdot (\tfrac{3}
{2})^{\tfrac{{n^2 (n - 1)}}
{2}} \cdot \log ^2 A)
, where n is the rank of the lattice and A is maximal norm of the input base vectors. This is an O(log2
A) algorithm which can be used to compute Minkowski reduced bases for the fixed rank lattices. A time complexity n! · 3
n
(log A)
O(1) algorithm which can be used to compute the successive minima with the help of the dual Hermite-Korkin-Zolotarev base was
given by Blomer in 2000 and improved to the time complexity n! · (log A)
O(1) by Micciancio in 2008. The algorithm in this paper is more suitable for computing the Minkowski reduced bases of low rank
lattices with very large base vector sizes. 相似文献
14.
Assume that we want to recover $f : \Omega \to {\bf C}$ in the
$L_r$-quasi-norm ($0 < r \le \infty$) by a linear sampling method
$$
S_n f = \sum_{j=1}^n f(x^j) h_j ,
$$
where $h_j \in L_r(\Omega )$ and $x^j \in \Omega$
and $\Omega \subset {\bf R}^d$ is an arbitrary bounded Lipschitz domain.
We assume that $f$ is from the unit ball of
a Besov space $B^s_{pq} (\Omega)$ or of a
Triebel--Lizorkin space $F^s_{pq} (\Omega)$ with
parameters such that the space is compactly embedded
into $C(\overline{\Omega})$. We prove that the optimal rate
of convergence of linear sampling methods is
$$
n^{ -{s}/{d} + ({1}/{p}-{1}/{r})_+} ,
$$
nonlinear methods do not yield a better rate.
To prove this we use a result from Wendland (2001) as well
as results concerning the spaces $B^s_{pq} (\Omega) $ and $F^s_{pq}(\Omega)$.
Actually, it is another aim of this paper to complement the
existing literature about the function spaces $B^s_{pq} (\Omega)$ and $F^s_{pq}
(\Omega)$ for bounded Lipschitz domains $\Omega \subset {\bf R}^d$.
In this sense, the paper is also a continuation of a paper by Triebel (2002). 相似文献
15.
Xiaodong Zheng 《Proceedings of the American Mathematical Society》1998,126(12):3669-3679
Confidence interval construction for parameters of lattice distributions is considered. By using saddlepoint formulas and bootstrap calibration, we obtain relatively short intervals and bounds with coverage errors, in contrast with and coverage errors for normal theory intervals and bounds when the population distribution is absolutely continuous. Closed form solutions are also provided for the cases of binomial and Poisson distributions. The method is illustrated by some simulation results.
16.
Based on the generalized Dikin-type direction proposed by Jansen et al in 1997, we give out in this paper a generalized Dinkin-type affine scaling algorithm for solving the $P_*(k)$-matrix linear complementarity problem (LCP). By using high-order correctors technique and rank-one updating, the iteration complexity and the total computational turn out asymptotically $O((\kappa+1)\sqrt{n}L)$ and $O((\kappa+1)n^3L)$ respectively. 相似文献
17.
It is shown that every homogeneous set of n points in d-dimensional Euclidean space determines at least
distinct distances for a constant c(d) > 0. In three-space the above general bound is slightly improved and it is shown that every homogeneous set of n points
determines at least
distinct distances. 相似文献
18.
19.
Hengcai TANG 《数学年刊B辑(英文版)》2016,37(5):793-802
Let f be a holomorphic Hecke eigenform of weight k for the modular groupΓ = SL2(Z) and let λf(n) be the n-th normalized Fourier coefficient. In this paper, by a new estimate of the second integral moment of the symmetric square L-function related to f, the estimate 1λf(n21) x2 k2(log(x + k))6n≤x is established, which improves the previous result. 相似文献
20.
We address the asymptotic behaviour of the vibrations of a body occupying a domain $\Omega\subset\mathbb{R}^n, n=2,3$. The density, which depends on a small parameter $\varepsilon$\nopagenumbers\end , is of the order $O(1)$\nopagenumbers\end out of certain regions where it is $O(\varepsilon^{‐m})$\nopagenumbers\end with $m>2$\nopagenumbers\end . These regions, the concentrated masses with diameter $O(\varepsilon)$\nopagenumbers\end , are located near the boundary, at mutual distances $O(\eta)$\nopagenumbers\end , with $\eta=\eta(\varepsilon)\rightarrow 0$\nopagenumbers\end . We impose Dirichlet (resp. Neumann) conditions at the points of $\partial\Omega$\nopagenumbers\end in contact with (resp. out of) the masses. We look at the asymptotic behaviour, as $\varepsilon\rightarrow 0$\nopagenumbers\end , of the eigenvalues of order $O(1)$\nopagenumbers\end , the high frequencies, of the corresponding eigenvalue problem. We show that they accumulate on the whole positive real axis and characterize those giving rise to global vibrations of the whole system. We use the fact that the corresponding eigenfunctions, microscopically, present a skin effect in the concentrated masses. Copyright © 2001 John Wiley & Sons, Ltd. 相似文献