共查询到20条相似文献,搜索用时 15 毫秒
1.
A special case of Mahler's conjecture on the volume-product of symmetric convex bodies in n -dimensional Euclidean space is treated here. This is the case of polytopes with at most 2n+2 vertices (or facets). Mahler's conjecture is proved in this case for n≤ 8 and the minimal bodies are characterized.
<lsiheader>
<onlinepub>7 August, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>20n2p163.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>no
<sectionname>
</lsiheader>
Received May 28, 1996, and in revised form November 7, 1996. 相似文献
2.
T. K. Dey 《Discrete and Computational Geometry》1998,19(3):373-382
We prove an O(n(k+1)
1/3
) upper bound for planar k -sets. This is the first considerable improvement on this bound after its early solution approximately 27 years ago. Our
proof technique also applies to improve the current bounds on the combinatorial complexities of k -levels in the arrangement of line segments, k convex polygons in the union of n lines, parametric minimum spanning trees, and parametric matroids in general.
<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>19n3p373.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received May 31, 1997, and in revised form June 30, 1997. 相似文献
3.
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. 相似文献
4.
B. Solomyak 《Discrete and Computational Geometry》1998,20(2):265-279
Let be a translationally finite self-similar tiling of R
d
. We prove that if is nonperiodic, then it has the unique composition property. More generally, has the unique composition property modulo the group of its translation symmetries.
<lsiheader>
<onlinepub>7 August, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>20n2p265.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>no
<sectionname>
</lsiheader>
Received August 7, 1996, and in revised form December 18, 1996. 相似文献
5.
Let g(n) denote the least integer such that among any g(n) points in general position in the plane there are always n in convex position. In 1935, P. Erdős and G. Szekeres showed that g(n) exists and . Recently, the upper bound has been slightly improved by Chung and Graham and by Kleitman and Pachter. In this paper we
further improve the upper bound to
<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>19n3p457.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received July 1, 1997, and in revised form July 14, 1997. 相似文献
6.
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. 相似文献
7.
G. Csizmadia 《Discrete and Computational Geometry》1998,20(2):179-187
Let F=F(n) denote the largest number such that any set of n points in the plane with minimum distance 1 has at least F elements, no two of which are at unit distance. Improving a result by Pollack, we show that F(n)≥ (9/35)n . We also give an O(n log n) time algorithm for selecting at least (9/35)n elements in a set of n points with minimum distance 1 so that no two selected points are at distance 1.
<lsiheader>
<onlinepub>7 August, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>20n2p179.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>no
<sectionname>
</lsiheader>
Received June 12, 1996, and in revised form April 22, 1997. 相似文献
8.
Isosceles Planar Subsets 总被引:2,自引:0,他引:2
P. Fishburn 《Discrete and Computational Geometry》1998,19(3):391-398
A finite planar set is k -isosceles for k ≥ 3 if every k -point subset of the set contains a point equidistant from two others. There are three nonsimilar 3-isosceles sets with five
points and one with six points. Eleven 4-isosceles sets with eight points are noted, and it is conjectured that no 4-isosceles
set has nine points. Exactly one 4-isosceles 8-set has four points on a line, and every 4-isosceles set that includes the
vertices of a square has fewer than eight points.
<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>19n3p391.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received February 1, 1997, and in revised form June 24, 1997. 相似文献
9.
D. Ismailescu 《Discrete and Computational Geometry》1998,20(2):251-263
We prove that for every convex disk in the plane there exists a double-lattice covering of the plane with copies of with density ≤ 1.2281772 . This improves the best previously known upper bound ≤ 8/(3+2\sqrt{3}) 1.2376043 , due to Kuperberg, but it is still far from the conjectured value .
<lsiheader>
<onlinepub>7 August, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>20n2p251.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>no
<sectionname>
</lsiheader>
Received June 1, 1996, and in revised form January 24, 1997. 相似文献
10.
We consider two general principles which allow us to reduce certain additive problems for residue classes modulo a prime
to the corresponding problems for integers.
<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>19n3p343.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received January 21, 1997, and in revised form April 9, 1997. 相似文献
11.
G. Elekes 《Discrete and Computational Geometry》1998,19(3):383-389
Problems and results on polynomials of two variables which take few distinct values on finite Cartesian products are considered.
The methods we use come from combinatorial geometry.
<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>19n3p383.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received January 6, 1997, and in revised form June 13, 1997. 相似文献
12.
P. Brass 《Discrete and Computational Geometry》1998,19(3):355-366
We study the problem of the maximum number of unit distances among n points in the plane, under the additional restriction that we count only those unit distances that occur in a fixed set
of k directions, taking the maximum over all sets of n points and all sets of k directions. We prove that, for fixed k and sufficiently large n > n
0
(k) , the extremal sets are essentially sections of lattices, bounded by edges parallel to the k directions and of equal length.
<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>19n3p355.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received January 10, 1997, and in revised form May 16, 1997. 相似文献
13.
I. Talata 《Discrete and Computational Geometry》1998,19(3):447-455
The translative kissing number H(K) of a d -dimensional convex body K is the maximum number of mutually nonoverlapping translates of K which touch K . In this paper we show that there exists an absolute constant c > 0 such that H(K)≥ 2
cd
for every positive integer d and every d -dimensional convex body K . We also prove a generalization of this result for pairs of centrally symmetric convex bodies.
<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>19n3p447.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received February 18, 1997, and in revised form April 15, 1997. 相似文献
14.
A geometric graph is a graph G=G(V,E) drawn in the plane, where its vertex set V is a set of points in general position and its edge set E consists of straight segments whose endpoints belong to V . Two edges of a geometric graph are in convex position if they are disjoint edges of a convex quadrilateral. It is proved
here that a geometric graph with n vertices and no edges in convex position contains at most 2n-1 edges. This almost solves a conjecture of Kupitz. The proof relies on a projection method (which may have other applications)
and on a simple result of Davenport—Schinzel sequences of order 2.
<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>19n3p399.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received December 18, 1995, and in revised form June 17, 1997. 相似文献
15.
We consider the Newton polytope Σ(m,n) of the product of all minors of an m× n matrix of indeterminates. Using the fact that this polytope is the secondary polytope of the product Δ
m-1
×Δ
n-1
of simplices, and thus has faces corresponding to coherent polyhedral subdivisions of Δ
m-1
×Δ
n-1
, we study facets of Σ(m,n) , which correspond to the coarsest, nontrivial such subdivisions. We make use of the relation between secondary and fiber
polytopes, which in this case gives a representation of Σ(m,n) as the Minkowski average of all m × n transportation polytopes.
<lsiheader>
<onlinepub>7 August, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>20n2p231.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>no
<sectionname>
</lsiheader>
Received August 7, 1996, and in revised form April 4, 1997. 相似文献
16.
Consider the d -dimensional euclidean space E
d
. Two main results are presented: First, for any N∈
N, the number of types of periodic equivariant tilings that have precisely N orbits of (2,4,6, . . . ) -flags with respect to the symmetry group Γ , is finite. Second, for any N∈
N, the number of types of convex, periodic equivariant tilings that have precisely N orbits of tiles with respect to the symmetry group Γ , is finite. The former result (and some generalizations) is proved combinatorially, using Delaney symbols, whereas the proof
of the latter result is based on both geometric arguments and Delaney symbols.
<lsiheader>
<onlinepub>7 August, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>20n2p143.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>no
<sectionname>
</lsiheader>
Received September 5, 1996, and in revised form January 6, 1997. 相似文献
17.
M. Laczkovich 《Discrete and Computational Geometry》1998,19(3):411-425
Let A be a polygon, and let s (A) denote the number of distinct nonsimilar triangles Δ such that A can be dissected into finitely many triangles similar to Δ . If A can be decomposed into finitely many similar symmetric trapezoids, then s(A)=∞ . This implies that if A is a regular polygon, then s(A)=∞ . In the other direction, we show that if s(A)=∞ , then A can be decomposed into finitely many symmetric trapezoids with the same angles.
We introduce the following classification of tilings: a tiling is regular if Δ has two angles, α and β , such that at each vertex of the tiling the number of angles α is the same as that of β . Otherwise the tiling is irregular. We prove that for every polygon A the number of triangles that tile A irregularly is at most c ⋅ n
6
, where n is the number of vertices of A. If A has a regular tiling, then A can be decomposed into finitely many symmetric trapezoids with the same angles.
<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>19n3p411.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received February 17, 1997, and in revised form June 16, 1997. 相似文献
18.
P. Valtr 《Discrete and Computational Geometry》1998,19(3):461-469
A geometric graph is a graph G=(V,E) drawn in the plane so that the vertex set V consists of points in general position and the edge set E consists of straight-line segments between points of V . Two edges of a geometric graph are said to be parallel if they are opposite sides of a convex quadrilateral.
In this paper we show that, for any fixed k ≥ 3 , any geometric graph on n vertices with no k pairwise parallel edges contains at most O(n) edges, and any geometric graph on n vertices with no k pairwise crossing edges contains at most O(n log n) edges. We also prove a conjecture by Kupitz that any geometric graph on n vertices with no pair of parallel edges contains at most 2n-2 edges.
<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>19n3p461.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received January 27, 1997, and in revised form March 4, 1997, and June 16, 1997. 相似文献
19.
Let F denote a family of pairwise disjoint convex sets in the plane. F is said to be in convex position if none of its members is contained in the convex hull of the union of the others. For any fixed k≥ 3 , we estimate P
k
(n) , the maximum size of a family F with the property that any k members of F are in convex position, but no n are. In particular, for k=3 , we improve the triply exponential upper bound of T. Bisztriczky and G. Fejes Tóth by showing that P
3
(n) < 16
n
.
<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>19n3p437.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received March 27, 1997, and in revised form July 10, 1997. 相似文献
20.
P. K. Agarwal B. Aronov T. M. Chan M. Sharir 《Discrete and Computational Geometry》1998,19(3):315-331
We consider the problem of bounding the complexity of the k th level in an arrangement of n curves or surfaces, a problem dual to, and an extension of, the well-known k-set problem. Among other results, we prove a new bound, O(nk
5/3
) , on the complexity of the k th level in an arrangement of n planes in R
3
, or on the number of k -sets in a set of n points in three dimensions, and we show that the complexity of the k th level in an arrangement of n line segments in the plane is , and that the complexity of the k th level in an arrangement of n triangles in 3-space is O(n
2
k
5/6
α(n/k)) .
<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>19n3p315.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>yes
<sectionname>
</lsiheader>
Received February 7, 1997, and in revised form May 15, 1997, and August 30, 1997. 相似文献