Empty Convex Hexagons in Planar Point Sets

Erdős asked whether every sufficiently large set of points in general position in the plane contains six points that form a convex hexagon without any points from the set in its interior. Such a configuration is called an empty convex hexagon. In this paper, we answer the question in the affirmative. We show that every set that contains the vertex set of a convex 9-gon also contains an empty convex hexagon.     

Distance Sets of Well-Distributed Planar Point Sets

We prove that a well-distributed subset of ${\Bbb R}^2$ can have a distance set $\Delta$ with $\#(\Delta\cap [0,N])\leq CN^{3/2-\epsilon}$ only if the distance is induced by a polygon $K$. Furthermore, if the above estimate holds with $\epsilon=\frac12$, then $K$ can have only finitely many sides.     

Empty Monochromatic Simplices

Let S be a k-colored (finite) set of n points in $\mathbb{R}^{d}$ , d≥3, in general position, that is, no (d+1) points of S lie in a common (d?1)-dimensional hyperplane. We count the number of empty monochromatic d-simplices determined by S, that is, simplices which have only points from one color class of S as vertices and no points of S in their interior. For 3≤k≤d we provide a lower bound of $\varOmega(n^{d-k+1+2^{-d}})$ and strengthen this to Ω(n ^d?2/3) for k=2. On the way we provide various results on triangulations of point sets in  $\mathbb{R}^{d}$ . In particular, for any constant dimension d≥3, we prove that every set of n points (n sufficiently large), in general position in $\mathbb{R}^{d}$ , admits a triangulation with at least dn+Ω(logn) simplices.     

Covering Paths for Planar Point Sets

Given n points in the plane, a covering path is a polygonal path that visits all the points. If no three points are collinear, every covering path requires at least n/2 segments, and n?1 straight line segments obviously suffice even if the covering path is required to be noncrossing. We show that every set of n points in the plane admits a (possibly self-crossing) covering path consisting of n/2+O(n/logn) straight line segments. If the path is required to be noncrossing, we prove that (1?ε)n straight line segments suffice for a small constant ε>0, and we exhibit n-element point sets that require at least 5n/9?O(1) segments in every such path. Further, the analogous question for noncrossing covering trees is considered and similar bounds are obtained. Finally, it is shown that computing a noncrossing covering path for n points in the plane requires Ω(nlogn) time in the worst case.     

Open Caps and Cups in Planar Point Sets

Points p₁,p₂,...,p_k in the plane, ordered in the x-direction, form a k-cap (k-cup}, respectively) if they are in convex position and p₂,...,p_k-1 lie all above (below, respectively) the segment p₁p_k. We prove the following generalization of the Erdos-Szekeres theorem. For any k, any sufficiently large set P of points in general position contains k points, p₁1,p₂,...,p_k, that form either a k-cap or a k-cup, and there is no point of P vertically above the polygonal line p₁p₂···p_k. We give double-exponential lower and upper bounds on the minimal size of P. We also give several related results.     

Planar Point Sets With Large Minimum Convex Decompositions

We show the existence of sets with $n$ points ( $n\ge 4$ ) for which every convex decomposition contains more than $\frac{35}{32}n-\frac{3}{2}$ polygons, which refutes the conjecture that for every set of $n$ points there is a convex decomposition with at most $n+C$ polygons. For sets having exactly three extreme points we show that more than $n+\sqrt{2(n-3)}-4$ polygons may be necessary to form a convex decomposition.     

关于平面19-点集的空凸分划问题

主要研究了平面上处于一般位置的19-点集,根据其凸包边数的不同,分别讨论了其所含空凸多边形的个数,得出G(19)≤5.在此基础上,对平面上处于一般位置的n-点集得出G(n)≤[11n/42],从而改进了G(n)的上界.     

Note – On the Number of Triangulations of Planar Point Sets

n points in the plane is at most . Received: November 1, 1995     

Almost Combinatorial Selector Sets

Classes of subsets of positive integers based on the notion of selector functions similar to the Jockusch selector of a semirecursive set are studied.     

几乎良紧集

在Ｌ－ｆｕｚｚｙ拓扑空间中提出了几乎良紧集的概念，研究了它的基本特征，讨论了它的性质，通过若干例揭示了几乎良紧性与其它一些Ｆｕｚｚｙ几乎紧性之间的联系。     

Covering Planar Sets

Doklady Mathematics - Methods for improving upper and lower bounds for various coverings of planar sets are proposed. New bounds for various numbers of partition constituents are presented, and...     

Almost Planar Waves in Anisotropic Media

We investigate corners and steps of interfaces in anisotropic systems. Starting from a stable planar front in a general reaction-diffusion-convection system, we show existence of almost planar interior and exterior corners. When the interface propagation is unstable in some directions, we show that small steps in the interface may persist. Our assumptions are based on physical properties of interfaces such as linear and nonlinear dispersion, rather than properties of the modeling equations such as variational or comparison principles. We also give geometric criteria based on the Cahn–Hoffman vector, that distinguish between the formation of interior and exterior corners.     

Monochromatic Matchings in the Shadow Graph of Almost Complete Hypergraphs

Edge colorings of r-uniform hypergraphs naturally define a multicoloring on the 2-shadow, i.e., on the pairs that are covered by hyperedges. We show that in any (r – 1)-coloring of the edges of an r-uniform hypergraph with n vertices and at least (1-e)( *20c nr)(1-\varepsilon)\left( {\begin{array}{*{20}c} n\\ r\\ \end{array}}\right) edges, the 2-shadow has a monochromatic matching covering all but at most o(n) vertices. This result confirms an earlier conjecture and implies that for any fixed r and sufficiently large n, there is a monochromatic Berge-cycle of length (1 – o(1))n in every (r – 1)-coloring of the edges of K^(r)_n{K^{(r)}_{n}}, the complete r-uniform hypergraph on n vertices.     

Extremal Convex Planar Sets

Each convex planar set K has a perimeter C, a minimum width E, an area A, and a diameter D. The set of points (E,C, A^1/2, D) corresponding to all such sets is shown to occupy a cone in the non-negative orthant of R⁴with its vertex at the origin. Its three-dimensional cross section S in the plane D = 1 is investigated. S lies in a rectangular parallelepiped in R³. Results of Lebesgue, Kubota, Fukasawa, Sholander, and Hemmi are used to determine some of the boundary surfaces of S, and new results are given for the other boundary surfaces. From knowledge of S, all inequalities among E, C ,A, and D can be found.     

Almost Cross-Intersecting and Almost Cross-Sperner Pairs of Families of Sets

For a set G and a family of sets ${\mathcal{F}}$ let ${\mathcal{D}_{\mathcal{F}}(G)=\{F\in \mathcal{F}:F\cap G=\emptyset\}}$ and ${\mathcal{S}_{\mathcal{F}}(G)=\{F\in\mathcal{F}:F\subseteq G\,{\rm or} \,G \subseteq F\}.}$ We say that a family is l-almost intersecting, (≤ l)-almost intersecting, l-almost Sperner, (≤ l)-almost Sperner if ${|\mathcal{D}_{\mathcal{F}}(F)|=l, |\mathcal{D}_{\mathcal{F}}(F)|\le l, |\mathcal{S}_{\mathcal{F}}(F)|=l, |\mathcal{S}_{\mathcal{F}}(F)| \le l}$ (respectively) for all ${F \in \mathcal{F}.}$ We consider the problem of finding the largest possible family for each of the above properties. We also address the analogous generalization of cross-intersecting and cross-Sperner families.     

About 4-Isosceles Planar Sets

A finite planar set is k -isosceles for k \geq 3 , if every k -point subset of the set contains a point equidistant from the other two. This paper gives affirmative answers to a few open problems about 4-isosceles sets. Received August 14, 2001, and in revised form September 10, 2001. Online publication December 21, 2001.     

L-fuzzy拓扑空间中的几乎可数仿紧性

以可数仿紧性为背景,介绍几乎可数仿紧性的定义,并刻画其基本特征.深入研究L-fuzzy几乎可数仿紧性的性质,并证明几乎可敷仿紧性是"L-好的推广".