共查询到20条相似文献,搜索用时 46 毫秒
1.
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
. 相似文献
2.
In this paper we show that there exists a
-coreset for k-median and k-means clustering of n points in
which is of size independent of n. In particular, we construct a
-coreset of size
for k-median clustering, and of size
for k-means clustering. 相似文献
3.
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. 相似文献
4.
Arthur D. Grainger 《Semigroup Forum》2006,73(2):234-242
Let J be an infinite set and let
, i.e., I is the collection of all non empty finite subsets of
J. Let
denote the collection of all ultrafilters on the set I and let
be the compact (Hausdorff) right topological semigroup that is the Stone-Cech Compactification of the semigroup
equipped with the discrete topology. This paper continues the study of
that was started in [3] and [5]. In [5], Koppelberg established that
(where K( S) is the smallest ideal of a semigroup S) and for non empty
she established
. In this note, we show that for
such that
is infinite,
is a proper subset of
and
, where
. 相似文献
5.
We find lower bounds for linear and Alexandrov's cowidths of Sobolev's classes on Compact Riemannian homogeneous manifolds
. Using these results we give an explicit solution of the problem of optimal reconstruction of functions from Sobolev's classes
in
. 相似文献
6.
Jesus Jeronimo Castro 《Discrete and Computational Geometry》2007,37(3):409-417
Let
be a family of convex figures in the plane. We say that
has property T if there exists a line intersecting every member of
. Also, the family
has property T(k) if every k-membered subfamily of
has property T. Let B be the unit disc centered at the origin. In this paper we prove that if a finite family
of translates of B has property T(4) then the family
, where
, has property T. We also give some results concerning families of translates of the unit disc which has either property T(3)
or property T(5). 相似文献
7.
In this article we show that the distributional point values of a tempered distribution are characterized by their Fourier
transforms in the following way: If
and
, and
is locally integrable, then
distributionally if and only if there exists k such that
, for each a > 0, and similarly in the case when
is a general distribution. Here
means in the Cesaro sense. This result generalizes the characterization of Fourier series of distributions with a distributional
point value given in [5] by
. We also show that under some extra conditions, as if the sequence
belongs to the space
for some
and the tails satisfy the estimate
,\ as
, the asymmetric partial sums\ converge to
. We give convergence results in other cases and we also consider the convergence of the asymmetric partial integrals. We
apply these results to lacunary Fourier series of distributions. 相似文献
8.
In this paper we study the worst-case error (of numerical integration) on the unit sphere
for all functions in the unit ball of the Sobolev space
where
More precisely, we consider infinite sequences
of m(n)-point numerical integration rules
where: (i)
is exact for all spherical polynomials of degree
and (ii)
has positive weights or, alternatively to (ii), the sequence
satisfies a certain local regularity property. Then we show that the worst-case error (of numerical integration)
in
has the upper bound
where the constant c depends on s and d (and possibly the sequence
This extends the recent results for the sphere
by K. Hesse and I.H. Sloan to spheres
of arbitrary dimension
by using an alternative representation of the worst-case error. If the sequence
of numerical integration rules satisfies
an order-optimal rate of convergence is achieved. 相似文献
9.
Given a collection S of subsets of some set
and
the set cover problem is to find the smallest subcollection
that covers
that is,
where
denotes
We assume of course that S covers
While the general problem is NP-hard to solve, even approximately, here we consider some geometric special cases, where usually
Combining previously known techniques [4], [5], we show that polynomial-time approximation algorithms with provable performance
exist, under a certain general condition: that for a random subset
and nondecreasing function f(·), there is a decomposition of the complement
into an expected at most f(|R|) regions, each region of a particular simple form. Under this condition, a cover of size O(f(|C|))
can be found in polynomial time. Using this result, and combinatorial geometry results implying bounding functions f(c) that
are nearly linear, we obtain o(log c) approximation algorithms for covering by fat triangles, by pseudo-disks, by a family
of fat objects, and others. Similarly, constant-factor approximations follow for similar-sized fat triangles and fat objects,
and for fat wedges. With more work, we obtain constant-factor approximation algorithms for covering by unit cubes in
and for guarding an x-monotone polygonal chain. 相似文献
10.
Regular Semigroups with Inverse Transversals 总被引:2,自引:0,他引:2
Fenglin Zhu 《Semigroup Forum》2006,73(2):207-218
Let C be a semiband with an inverse transversal
. In [7], G.T. Song and F.L. Zhu construct a fundamental regular semigroup
with an inverse transversal
.
is isomorphic to a subsemigroup of the Hall semigroup of C but it is easier to handle. Its elements are partial transformations,
and the operation-although not the usual composition-is defined by means of composition. Any full regular subsemigroup T of
is a fundamental regular semigroup with inverse transversal
. Moreover, any regular semigroup S with an inverse transversal
is proved to be an idempotent-separating coextension of a full regular subsemigroup T of some
. By means of a full
regular subsemigroup T of some
and by means of an inverse semigroup K satisfying some conditions, in this paper, we construct a regular semigroup
with inverse transversal
such that
is isomorphic to K and
to T. Furthermore, it is proved that if S is a regular semigroup with an inverse transversal
then S can be constructed from the corresponding T and from
in this way. 相似文献
11.
We show that every function in the Hardy space can be approximated by linear combinations of translates and dilates of a synthesizer
, provided only that
and
satisfies a mild regularity condition. Explicitly, we prove scale averaged approximation for each
,
where
is an arbitrary lacunary sequence (such as
) and the coefficients
are local averages of f. This formula holds in particular if the synthesizer
is in the Schwartz class, or if it has compact support and belongs to
for some
in terms of differences of
. 相似文献
12.
MohammadHossein Bateni Erik D. Demaine MohammadTaghi Hajiaghayi Mohammad Moharrami 《Discrete and Computational Geometry》2007,38(3):615-637
Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood.
Motivated by applications in visualization, ad-hoc networks, and molecular reconstruction, we consider the natural problem
of embedding shortest-path metrics of unweighted planar graphs (planar graph metrics) into the Euclidean plane. It is known
that, in the special case of shortest-path metrics of trees, embedding into the plane requires
distortion in the worst case [M1], [BMMV], and surprisingly, this worst-case upper bound provides the best known approximation
algorithm for minimizing distortion. We answer an open question posed in this work and highlighted by Matousek [M3] by proving
that some planar graph metrics require
distortion in any embedding into the plane, proving the first separation between these two types of graph metrics. We also
prove that some planar graph metrics require
distortion in any crossing-free straight-line embedding into the plane, suggesting a separation between low-distortion plane
embedding and the well-studied notion of crossing-free straight-line planar drawings. Finally, on the upper-bound side,
we prove that all outerplanar graph metrics can be embedded into the plane with
distortion, generalizing the previous results on trees (both the worst-case bound and the approximation algorithm) and building
techniques for handling cycles in plane embeddings of graph metrics. 相似文献
13.
Let
be a nontrivial probability measure on the unit circle
the density of its absolutely continuous part,
its Verblunsky coefficients, and
its monic orthogonal polynomials. In this paper we compute the coefficients of
in terms of the
. If the function
is in
, we do the same for its Fourier coefficients. As an application we prove that if
and if
is a polynomial, then with
and S the left-shift operator on sequences we have
We also study relative ratio asymptotics of the reversed polynomials
and provide a necessary and sufficient condition in terms of the Verblunsky coefficients of the measures
and
for this difference to converge to zero uniformly on compact subsets of
. 相似文献
14.
Daniel A. Klain 《Discrete and Computational Geometry》2006,36(3):457-477
Hyperbolic area is characterized as the unique continuous isometry-invariant simple valuation on convex polygons in
We then show that continuous isometry-invariant simple valuations on polytopes in
for
are determined uniquely by their values at ideal simplices. The proofs exploit a connection between valuation theory in
hyperbolic space and an analogous theory on the Euclidean sphere. These results lead to characterizations of continuous isometry-invariant
valuations on convex polytopes and convex bodies in the hyperbolic plane
a partial characterization in
and a mechanism for deriving many fundamental theorems of hyperbolic integral geometry, including kinematic formulas,
containment theorems, and isoperimetric and Bonnesen-type inequalities. 相似文献
15.
Let
denote the linear space over
spanned by
. Define the (real) inner product
, where V satisfies: (i) V is real analytic on
; (ii)
; and (iii)
. Orthogonalisation of the (ordered) base
with respect to
yields the even degree and odd degree orthonormal Laurent polynomials
, and
. Define the even degree and odd degree monic orthogonal Laurent polynomials:
and
. Asymptotics in the double-scaling limit
such that
of
(in the entire complex plane),
, and
(in the entire complex plane) are obtained by formulating the odd degree monic orthogonal Laurent polynomial problem as a
matrix Riemann-Hilbert problem on
, and then extracting the large-n behaviour by applying the non-linear steepest-descent method introduced in [1] and further
developed in [2],[3]. 相似文献
16.
Adrian Dumitrescu 《Discrete and Computational Geometry》2006,36(4):503-509
Given a set P of n points in convex position in the plane, we prove that there exists a point
such that the number
of distinct distances from p is at least
The best previous bound,
from 1952, is due to Moser. 相似文献
17.
Rostom Getsadze 《Journal of Fourier Analysis and Applications》2006,12(5):597-604
We prove the following theorem: For arbitrary
there exists a nonnegative
function
such that
and
almost everywhere on
where
is the double Walsh-Paley system.
This statement remains true also for the double trigonometric system. 相似文献
18.
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. 相似文献
19.
We give conditions on radial nonnegative weights $W_1We give conditions on radial nonnegative weights
and
on
, for which the a priori inequality
holds with constant independent of
. Here
is the Laplace-Beltrami operator on the sphere
. Due to the relation between
and the tangential component of the gradient,
, we obtain some "Morawetz-type" estimates for
on
. As a consequence we establish some new estimates for the free Schr?dinger propagator
, which may be viewed as certain refinements of the
-(super)smoothness estimates of Kato and Yajima. These results, in turn, lead to the well-posedness of the initial value problem
for certain time dependent first order spherical perturbations of the
dimensional Schr?dinger equation. 相似文献
20.
Zoltan Furedi 《Discrete and Computational Geometry》2007,38(2):273-288
Let
be a triangle and let
be a set of homothetic copies of
. We prove that
implies that there are positive and negative signs
and there exist translates of
that cover
. 相似文献