共查询到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.
Oswin Aichholzer Jesus Garcia David Orden Pedro Ramos 《Discrete and Computational Geometry》2007,38(1):1-14
We provide a new lower bound on the number of (≤ k)-edges of a set of n points in the plane in general position. We show that
for
the number of (≤ k)-edges is at least
which, for
, improves the previous best lower bound in [12]. As a main consequence, we obtain a new lower bound on the rectilinear crossing
number of the complete graph or, in other words, on the minimum number of convex quadrilaterals determined by n points in
the plane in general position. We show that the crossing number is at least
which improves the previous bound of
in [12] and approaches the best known upper bound
in [4]. The proof is based on a result about the structure of sets attaining the rectilinear crossing number, for which we
show that the convex hull is always a triangle. Further implications include improved results for small values of n. We extend
the range of known values for the rectilinear crossing number, namely by
and
. Moreover, we provide improved upper bounds on the maximum number of halving edges a point set can have. 相似文献
3.
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. 相似文献
4.
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]. 相似文献
5.
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. 相似文献
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.
This paper deals with the homogenization of a sequence of non-linear conductivity energies in a bounded open set
The energy density is of the same order as
where
is periodic, u is a vector-valued function in
and
The conductivity
is equal to 1 in the "hard" phases composed by
two by two disjoint-closure periodic sets while
tends uniformly to 0 in the "soft" phases composed by periodic thin layers which separate the hard phases. We prove that
the limit energy, according to γ-convergence, is a multi-phase functional equal to the sum of the homogenized energies (of
order 1) induced by the hard phases plus an interaction energy (of order 0) due to the soft phases. The number of limit phases
is less than or equal to N and is obtained by evaluating the γ-limit of the rescaled energy of density
in the torus. Therefore, the homogenization result is achieved by a double γ-convergence procedure since the cell problem
depends on ε. 相似文献
8.
For any fixed
we construct an orthonormal Schauder basis
for C[-1,1] consisting of algebraic polynomials
with
The orthogonality is with respect to the Chebyshev weight. 相似文献
9.
Mario Petrich 《Semigroup Forum》2007,75(1):45-69
A normal cryptogroup S is a completely regular semigroup in which
is a congruence and
is a normal band. We represent S as a strong semilattice of completely simple semigroups, and may set
For each
we set
and represent
by means of an h-quintuple
These parameters are used to characterize certain quasivarieties of normal cryptogroups. Specifically, we construct the lattice
of quasivarieties generated by the (quasi)varieties
and
This is the lattice generated by the lattice of quasivarieties of normal bands, groups and completely simple semigroups.
We also determine the B-relation on the lattice of all quasivarieties of normal cryptogroups. Each quasivariety studied is
characterized in several ways. 相似文献
10.
D.S. Lubinsky 《Constructive Approximation》2007,25(3):303-366
Assume
is not an integer. In papers published in 1913 and 1938,
S.~N.~Bernstein established the limit
Here
denotes the error in best uniform approximation of
by polynomials
of degree
. Bernstein proved that
is itself the error in best uniform approximation of
by entire functions of exponential type at most 1,
on the whole real line. We prove that the best approximating entire function
is unique, and satisfies an alternation property. We show that the scaled
polynomials of best approximation converge to this unique entire function.
We derive a representation for
, as well
as its
analogue for
. 相似文献
11.
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. 相似文献
12.
An affine pseudo-plane X is a smooth affine surface defined over
which is endowed with an
-fibration such that every fiber is irreducible and only one fiber is a multiple fiber. If there is a hyperbolic
-action on X and X is an
-surface, we shall show that the universal covering
is isomorphic to an affine hypersurface
in the affine 3-space
and X is the quotient of
by the cyclic group
via the action
where
and
It is also shown that a
-homology plane X with
and a nontrivial
-action is an affine pseudo-plane. The automorphism group
is determined in the last section. 相似文献
13.
Zachary Mesyan 《Semigroup Forum》2007,75(3):648-675
Let
be a countably infinite set,
the group of permutations of
, and
the monoid of self-maps of
. Given two subgroups
, let us write
if there exists a finite subset
such that the groups generated by
and
are equal. Bergman and Shelah showed that the subgroups which are closed in the function topology on S fall into exactly
four equivalence classes with respect to
. Letting
denote the obvious analog of
for submonoids of E, we prove an analogous result for a certain class of submonoids of E, from which the theorem for groups
can be recovered. Along the way, we show that given two subgroups
which are closed in the function topology on S, we have
if and only if
(as submonoids of E), and that
for every subgroup
(where
denotes the closure of G in the function topology in S and
its closure in the function topology in E). 相似文献
14.
15.
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. 相似文献
16.
C. Carton-Lebrun 《Journal of Fourier Analysis and Applications》1995,2(1):49-64
For
define
where
Pointwise estimates and weighted inequalities describing the local Lipschitz continuity
of
are established. Sufficient conditions are found
for the boundedness of
from
into
and a spherical restriction property is proved. A study of the moment subspaces of
is next developed in the one-variable case, for
locally integrable,
a.e. It includes a decomposition theorem and a complete classification of all possible sequences of moment subspaces in
Characterizations are also given for each class. Applications related to the approximation and decomposition of
are discussed. 相似文献
17.
Denote by
the real-linear span of
, where
Under the concept of left-monogeneity defined through the generalized
Cauchy-Riemann operator we obtain the direct sum decomposition of
where
is the right-Clifford module of finite linear combinations of functions of the form
, where, for
, the function R is a k- or
-homogeneous leftmonogenic
function, for
or
, respectively, and h is a function defined in [0,∞) satisfying a certain integrability condition in relation to k, the spaces
are invariant under Fourier transformation.
This extends the classical result for
. We also deduce explicit Fourier transform
formulas for functions of the form
refining Bochner’s formula for spherical k-harmonics. 相似文献
18.
Jacek Dziubanski 《Constructive Approximation》2008,27(3):269-287
Let
be the standard Laguerre functions of type a. We denote
. Let
and
be the semigroups associated with the orthonormal systems
and
. We say that a function f belongs to the Hardy space
associated with one of the semigroups if the corresponding maximal function belongs to
. We prove special atomic decompositions of the elements of the Hardy spaces. 相似文献
19.
A compact set
is staircase connected if every two points
can be connected by a polygonal path with sides parallel to the coordinate axes, which is both x-monotone and y-monotone.
denotes the smallest number of edges of such a path.
is an integer-valued metric on S. We investigate this metric and introduce stars and kernels. Our main result is that the
r-th kernel is nonempty, compact and staircase connected provided
. 相似文献
20.
Almost exponentially localized polynomial kernels are constructed on the unit ball
in
with weights
, by smoothing out the coefficients of the corresponding orthogonal projectors. These kernels are utilized to the design of
cubature formulas on
with respect to
and to the construction of polynomial tight frames in
(called needlets) whose elements have nearly exponential localization. 相似文献