共查询到20条相似文献,搜索用时 0 毫秒
1.
Lukács and András posed the problem of showing the existence of a set of n−2 points in the interior of a convex n-gon so that the interior of every triangle determined by three vertices of the polygon contains a unique point of S. Such sets have been called pebble sets by De Loera, Peterson, and Su. We seek to characterize all such sets for any given convex polygon in the plane.
We first consider a certain class of pebble sets, called peripheral because they consist of points that lie close to the boundary
of the polygon. We characterize all peripheral pebble sets, and show that for regular polygons, these are the only ones. Though
we demonstrate examples of polygons where there are other pebble sets, we nevertheless provide a characterization of the kinds
of points that can be involved in non-peripheral pebble sets. We furthermore describe algorithms to find such points. 相似文献
2.
V. V. Makeev 《Journal of Mathematical Sciences》2016,212(5):527-530
3.
Ray Shooting Amidst Convex Polygons in 2D 总被引:1,自引:0,他引:1
Pankaj K. Agarwal Micha Sharir 《Journal of Algorithms in Cognition, Informatics and Logic》1996,21(3):508-519
We consider the problem of ray shooting in a two-dimensional scene consisting ofmconvex polygons with a total ofnedges. We present a data structure that requiresO(mn log m) space and preprocessing time and that answers a ray shooting query inO(log2 m log2 n) time. If the polygons are pairwise disjoint, the space and preprocessing time can be improved toO((m2+n)log m) andO((m2+n log n)log m), respectively. Our algorithm also works for a collection of disjoint simple polygons. We also show that if we allow onlyO(n) space, a ray shooting query among a collection of disjoint simple polygons can be answered in timeO(m/[formula]1+ log2 n) time, for any >0. 相似文献
4.
Giacomo Michelacci 《Geometriae Dedicata》1997,66(3):357-368
A method for the reconstruction of boundary points of convex sets is provided starting from three X-ray pictures in two orthogonal directions and from a point. 相似文献
5.
In a seminal paper from 1935, Erdős and Szekeres showed that for each n there exists a least value g(n) such that any subset of g(n) points in the plane in general position must always contain the vertices of a convex n -gon. In particular, they obtained the bounds which have stood unchanged since then. In this paper we remove the +1 from the upper bound for n ≥ 4 .
<lsiheader>
<onlinepub>26 June, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>19n3p367.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received January 1, 1997, and in revised form June 6, 1997. 相似文献
6.
Epstein D. B. A.; Marden A.; Markovic V. 《Proceedings London Mathematical Society》2006,92(3):624-654
We make a detailed study of the relation of a euclidean convexregion C Dome (). The dome is the relative boundary, in theupper halfspace model of hyperbolic space, of the hyperbolicconvex hull of the complement of . The first result is to provethat the nearest point retraction r: Dome () is 2-quasiconformal.The second is to establish precise estimates of the distortionof r near . 2000 Mathematics Subject Classification 30C75,30F40, 30F45, 30F60. 相似文献
7.
Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α
1
, α
2
, . . . ,α
n
be positive real numbers such that α
1
+α
2
+ ⋅ ⋅ ⋅ +α
n
=1 and 0< α
i
≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T
1
, T
2
, . . . ,T
n
so that each T
i
satisfies the following three conditions: (i) area(T
i
)=α
i
× area(S) ; (ii) ℓ (T
i
∩ ∂ (S))= α
i
× ℓ (∂ (S)) ; and (iii) T
i
∩ ∂ (S) consists of exactly one continuous curve. 相似文献
8.
Finding Convex Sets Among Points in the Plane 总被引:1,自引:0,他引:1
Let g(n) denote the least value such that any g(n) points in the plane in general position contain the vertices of a convex n -gon. In 1935, Erdős and Szekeres showed that g(n) exists, and they obtained the bounds Chung and Graham have recently improved the upper bound by 1; the first improvement since the original Erdős—Szekeres paper.
We show that
<lsiheader>
<onlinepub>26 June, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>19n3p405.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received January 1, 1997, and in revised form June 6, 1997. 相似文献
9.
Abstract. For a region X in the plane, we denote by area(X) the area of X and by ℓ (∂ (X)) the length of the boundary of X . Let S be a convex set in the plane, let n ≥ 2 be an integer, and let α
1
, α
2
, . . . ,α
n
be positive real numbers such that α
1
+α
2
+ ⋅ ⋅ ⋅ +α
n
=1 and 0< α
i
≤ 1/2 for all 1 ≤ i ≤ n . Then we shall show that S can be partitioned into n disjoint convex subsets T
1
, T
2
, . . . ,T
n
so that each T
i
satisfies the following three conditions: (i) area(T
i
)=α
i
× area(S) ; (ii) ℓ (T
i
∩ ∂ (S))= α
i
× ℓ (∂ (S)) ; and (iii) T
i
∩ ∂ (S) consists of exactly one continuous curve. 相似文献
10.
Valtr 《Discrete and Computational Geometry》2002,28(4):671-682
Abstract. Let P be a set of points in general position in the plane. We say that P is k -convex if no triangle determined by P contains more than k points of P in the interior. We say that a subset A of P in convex position forms an empty polygon (in P ) if no point of P \ A lies in the convex hull of A . We show that for any k,n there is an N=N(k,n) such that any k -convex set of at least N points in general position in the plane contains an empty n -gon. We also prove an analogous statement in R
d
for each odd d≥ 3 . 相似文献
11.
Valtr 《Discrete and Computational Geometry》2008,28(4):671-682
Abstract. Let P be a set of points in general position in the plane. We say that P is k -convex if no triangle determined by P contains more than k points of P in the interior. We say that a subset A of P in convex position forms an empty polygon (in P ) if no point of P \ A lies in the convex hull of A . We show that for any k,n there is an N=N(k,n) such that any k -convex set of at least N points in general position in the plane contains an empty n -gon. We also prove an analogous statement in R
d
for each odd d≥ 3 . 相似文献
12.
G. Mielczarek 《Acta Mathematica Hungarica》1998,78(3):213-226
Let Q be a convex compact set in R2 with a non-empty interior. We denoteby C the family of all non-empty closed convex subsets of Q. The aim of thepaper is to characterize the extreme elements of C. 相似文献
13.
14.
L. P. Yushchenko 《Ukrainian Mathematical Journal》2000,52(12):1956-1963
We prove the existence of a function fcontinuous and convex on [–1, 1] and such that, for any sequence {p
n}
n= 1
of algebraic polynomials p
nof degree nconvex on [–1, 1], the following relation is true:
, where 4(t, f) is the fourth modulus of continuity of the function fand
. We generalize this result to q-convex functions. 相似文献
15.
Volz Marcus Brazil Marcus Ras Charl Thomas Doreen 《Journal of Optimization Theory and Applications》2020,186(1):102-133
Journal of Optimization Theory and Applications - We introduce the concept of an obstacle skeleton, which is a set of line segments inside a polygonal obstacle $$\omega $$ that can be used in place... 相似文献
16.
Mordechai Novick 《Discrete and Computational Geometry》2012,47(2):378-392
In 2005, Goodman and Pollack introduced the concept of an allowable interval sequence, a combinatorial object which encodes properties of a family of pairwise disjoint convex sets in the plane. They, Dhandapani, and Holmsen used this concept to address Tverberg’s (1,k)-separation problem: How many pairwise disjoint compact convex sets in the plane are required to guarantee that one can be separated by a line from k others? (Denote this number by f k .) A new proof was provided that f 2=5, a result originally obtained by Tverberg himself, and the application of allowable interval sequences to the case of general k was left as an open problem. Hope and Katchalski, using other methods, proved in 1990 that 3k?1≤f k ≤12(k?1). In this paper, we apply the method of allowable interval sequences to give an upper bound on f k of under 7.2(k?1), shrinking the range given by Hope and Katchalski by more than half. For a family of translates we obtain a tighter upper bound of approximately 5.8(k?1). 相似文献
17.
We study dual pairs of combinatorial face-to-face cell decompositions of the real projective plane P
2
such that their canonically induced cell decompositions on the 2-sphere S
2 form dual pairs of combinatorical types of convex polyhedra, and such that these dual pairs share two natural properties
with those induced by dual pairs of Platonic solids: (1) Every Petrie polygon is a finite simple closed polygon of length
2(n-1) for some fixed n. (2) Every pair of Petrie polygons has precisely two common edges. Such pairs of face-to-face cell decompositions of the
projective plane are in one-to-one correspondence with n-element pseudoline arrangements. We study in particular those dual pairs of cell decompositions in which has only 3-valent vertices, i.e., via the above one-to-one correspondence: p
3-maximal pseudoline arrangements. A p
3
-maximal pseudoline arrangement with n elements in turn determines a neighborly 2-manifold with Euler characteristic χ = n(7-n)/6, and vice versa, this neighborly 2-manifold uniquely determines its generating p
3
-maximal pseudoline arrangement. We provide new inductive constructions for finding infinite example classes of p
3-maximal pseudoline arrangements from small existing ones, we describe an algorithm for generating them, we provide a complete
list of existence up to n = 40, and we discuss their properties.
Received July 18, 1996, and in revised form October 28, 1996. 相似文献
18.
Let F= {C1,C2,...,C} be a family of ndisjoint convex bodies in the plane. We say that a set Vof exterior light sources illuminates F, if for every boundary point of any member of Fthere is a point in Vsuch that is visible from ,i.e. the open line segment joining and is disjoint from F. An illumination system Vis called primitive if no proper subset of Villuminates F. Let pmax(F) denote the maximum number of points forming a primitive illumination system for F, and letpmax(n) denote the minimum of F) taken over all families Fconsisting of ndisjoint convex bodies in the plane. The aim of this paper is to investigate the quantities pmax(F) and pmax(n). 相似文献
19.
Dedicated to the memory of Paul Erdős
Suppose we have a finite collection of closed convex sets in the plane, (which without loss of generality we can take to be
polygons). Suppose further that among any four of them, some three have non-empty intersection. We show that 13 points are
sufficient to meet every one of the convex sets.
Received October 27, 1999/Revised April 11, 2000
RID="*"
ID="*" Supported by grant OTKA-T-029074.
RID="†"
ID="†" Supported by NSF grant DMS-99-70071, OTKA-T-020914 and OTKA-F-22234. 相似文献
20.