共查询到20条相似文献,搜索用时 31 毫秒
1.
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
. 相似文献
2.
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
. 相似文献
3.
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). 相似文献
4.
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. 相似文献
5.
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. 相似文献
6.
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. 相似文献
7.
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. 相似文献
8.
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. 相似文献
9.
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
. 相似文献
10.
We present an algorithm for finding shortest surface non-separating cycles in graphs embedded on surfaces in
time, where V is the number of vertices in the graph and g is the genus of the surface. If
, this represents an improvement over previous results by Thomassen, and Erickson and Har-Peled. We also give algorithms to
find a shortest non-contractible cycle in
time, which improves previous results for fixed genus. This result can be applied for computing the face-width and the non-separating
face-width of embedded graphs. Using similar ideas we provide the first near-linear running time algorithm for computing the
face-width of a graph embedded on the projective plane, and an algorithm to find the face-width of embedded toroidal graphs
in
time. 相似文献
11.
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]. 相似文献
12.
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. 相似文献
13.
Scalar functions defined on a topological space
are at the core of many applications such as shape matching, visualization and physical simulations. Topological persistence
is an approach to characterizing these functions. It measures how long topological structures in the sub-level sets
persist as c changes. Recently it was shown that the critical values defining a topological structure with relatively large
persistence remain almost unaffected by small perturbations. This result suggests that topological persistence is a good measure
for matching and comparing scalar functions. We extend these results to critical points in the domain by redefining persistence
and critical points and replacing sub-level sets
with interval sets
. With these modifications we establish a stability result for critical points. This result is strengthened for maxima that
can be used for matching two scalar functions. 相似文献
14.
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. 相似文献
15.
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. 相似文献
16.
Rafal Latala Piotr Mankiewicz Krzysztof Oleszkiewicz Nicole Tomczak-Jaegermann 《Discrete and Computational Geometry》2007,38(1):29-50
We consider polytopes in
that are generated by N vectors in
whose coordinates are independent subgaussian random variables. (A particular case of such polytopes are symmetric random
polytopes generated by N independent vertices of the unit cube.) We show that for a random pair of such polytopes the Banach-Mazur
distance between them is essentially of a maximal order n. This result is an analogue of the well-known Gluskin's result
for spherical vectors. We also study the norms of projections on such polytopes and prove an analogue of Gluskin's and Szarek's
results on basis constants. The proofs are based on a version of "small ball" estimates for linear images of random subgaussian
vectors. 相似文献
17.
Mohan S. Putcha 《Semigroup Forum》2007,75(3):543-553
Let M be a finite monoid with unit group G. By the work of Munn and Ponizovski, the irreducible complex representations of
M are classified according to which J-class (apex) they come from. Consider the irreducible representations of M with apex
. These representations restrict to representations of G, whose components we view as coming from J-classes below G. The remaining
irreducible representations (and their characters) of G are called cuspidal. We show that an irreducible character
of G is cuspidal if and only if
for all idempotents
, where
. 相似文献
18.
James H. Schmerl 《Discrete and Computational Geometry》2007,38(1):155-167
Suppose n ≥ 2 and
are such that X is infinite and Y is the set of vertices of an n-simplex. Then there is blue/red coloring of
such that no set similar to X is monochromatically blue and no set similar to Y is monochromatically red. 相似文献
19.
Given a metric d on a finite set X, a realization of d is a weighted graph
with
such that for all
the length of any shortest path in G between x and y equals d(x,y). In this paper we consider two special kinds of realizations,
optimal realizations and hereditarily optimal realizations, and their relationship with the so-called tight span. In particular,
we present an infinite family of metrics {dk}k≥1, and—using a new characterization for when the so-called underlying graph of a metric is an optimal realization that we also
present—we prove that dk has (as a function of k) exponentially many optimal realizations with distinct degree sequences. We then show that this family
of metrics provides counter-examples to a conjecture made by Dress in 1984 concerning the relationship between optimal realizations
and the tight span, and a negative reply to a question posed by Althofer in 1988 on the relationship between optimal and hereditarily
optimal realizations. 相似文献
20.
We continue the investigation of some problems in learning theory in the setting formulated by F. Cucker and S. Smale. The
goal is to find an estimator
on the base of given data
that approximates well the regression function
of an unknown Borel probability measure
defined on
We assume that
belongs to a function class
It is known from previous works that the behavior of the entropy numbers
of
in the uniform norm
plays an important role in the above problem. The standard way of measuring the error between a target function
and an estimator
is to use the
norm (
is the marginal probability measure on X generated by
). This method has been used in previous papers. We continue to use this method in this paper. The use of the
norm in measuring the error has motivated us to study the case when we make an assumption on the entropy numbers
of
in the
norm. This is the main new ingredient of thispaper. We construct good estimators in different settings: (1) we know both
and
; (2) we know
but we do not know
and (3) we only know that
is from a known collection of classes but we do not know
An estimator from the third setting is called a universal estimator. 相似文献