共查询到20条相似文献,搜索用时 15 毫秒
1.
《Journal of Discrete Algorithms》2008,6(4):583-594
Assume that a set of imprecise points in the plane is given, where each point is specified by a region in which the point will lie. Such a region can be modelled as a circle, square, line segment, etc. We study the problem of maximising the area of the convex hull of such a set. We prove NP-hardness when the imprecise points are modelled as line segments, and give linear time approximation schemes for a variety of models, based on the core-set paradigm. 相似文献
2.
In this paper, we study properties of general closed convex sets that determine the closedness and polyhedrality of the convex hull of integer points contained in it. We first present necessary and sufficient conditions for the convex hull of integer points contained in a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the convex hull of integer points in general convex sets to be a polyhedron. This result generalizes the well-known result due to Meyer (Math Program 7:223–225, 1974). Under a simple technical assumption, we show that these sufficient conditions are also necessary for the convex hull of integer points contained in general convex sets to be a polyhedron. 相似文献
3.
4.
5.
6.
7.
T. M. Chan 《Discrete and Computational Geometry》1996,16(4):369-387
We use known data structures for ray-shooting and linear-programming queries to derive new output-sensitive results on convex
hulls, extreme points, and related problems. We show that thef-face convex hull of ann-point setP in a fixed dimensiond≥2 can be constructed in
time; this is optimal if
for some sufficiently large constantK. We also show that theh extreme points ofP can be computed in
time. These results are then applied to produce an algorithm that computes the vertices of all the convex layers ofP inO(n
2−γ) time for any constant
. Finally, we obtain improved time bounds for other problems including levels in arrangements and linear programming with
few violated constraints. In all of our algorithms the input is assumed to be in general position.
This research was supported by a Killam Predoctoral Fellowship and an NSERC Postgraduate Scholarship. 相似文献
8.
Summary. A general formula is proved, which relates the equiaffine inner parallel curves of a plane convex body and the probability
that the convex hull of j independent random points is disjoint from the convex hull of k further independent random points. This formula is applied to improve some well-known results in geometric probability. For
example, an estimate, which was established for a special case by L. C. G. Rogers, is obtained with the best possible bound,
and an asymptotic formula due to A. Rényi and R.␣Sulanke is extended to an asymptotic expansion.
Received: 21 May 1996 相似文献
9.
10.
Fuchang Gao 《Israel Journal of Mathematics》2001,123(1):359-364
LetT be a precompact subset of a Hilbert space. The metric entropy of the convex hull ofT is estimated in terms of the metric entropy ofT, when the latter is of order εℒ2. The estimate is best possible. Thus, it answers a question left open in [CKP]. 相似文献
11.
12.
13.
14.
John Wermer 《Arkiv f?r Matematik》1982,20(1-2):129-135
15.
Piet Groeneboom 《Probability Theory and Related Fields》1988,79(3):327-368
It is shown that the process of vertices of the convex hull of a uniform sample from the interior of a convex polygon converges locally, after rescaling, to a strongly mixing Markov process, as the sample size tends to infinity. The structure of the limiting Markov process is determined explicitly, and from this a central limit theorem for the number of vertices of the convex hull is derived. Similar results are given for uniform samples from the unit disk. 相似文献
16.
We show that ifP
, |P|=d+k,dk1 andO int convP, then there exists a simplexS of dimension
with vertices inP, satisfyingO rel intS, the bound being sharp. We give an upper bound for the minimal number of vertices of facets of a (j-1)-neighbourly convex polytope in
withv vertices.Research (partially) supported by Hung. Nat. Found. for Sci. Research, grant no. 1817Research (partially) supported by Hung. Nat. Found. for Sci. Research, grant no. 326-0213 相似文献
17.
Theprofile of a hypergraph onn vertices is (f
0, f1, ...,f
n) wheref
i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain
many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton). 相似文献
18.
José Rodríguez 《Mathematische Nachrichten》2007,280(11):1302-1309
Let (Ω, Σ, μ) be a complete probability space and let X be a Banach space. We consider the following problem: Given a function f: Ω → X for which there is a norming set B ? BX * such that Zf,B = {x * ○ f: x * ∈ B } is uniformly integrable and has the Bourgain property, does it follow that f is Birkhoff integrable? It turns out that this question is equivalent to the following one: Given a pointwise bounded family ?? ? ?Ω with the Bourgain property, does its convex hull co(??) have the Bourgain property? With the help of an example of D. H. Fremlin, we make clear that both questions have negative answer in general. We prove that a function f: Ω → X is scalarly measurable provided that there is a norming set B ? BX * such that Zf,B has the Bourgain property. As an application we show that the first problem has positive solution in several cases, for instance: (i) when BX * is weak* separable; (ii) under Martin's axiom, for functions defined on [0, 1] with values in a Banach space with density character smaller than the continuum. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
19.
20.
Kallrath Josef Ryu Joonghyun Song Chanyoung Lee Mokwon Kim Deok-Soo 《Journal of Global Optimization》2021,80(3):551-594
Journal of Global Optimization - The minimal convex hulls of disks problem is to find such arrangements of circular disks in the plane that minimize the length of the convex hull boundary. The... 相似文献