اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدEvery Large Point Set contains Many Collinear Points or an Empty Pentagon
247
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We prove the following generalised empty pentagon theorem: for every integer $ell geq 2$, every sufficiently large set of points in the plane contains $ell$ collinear points or an empty pentagon. As an application, we settle the next open case of the big line or big clique conjecture of Kara, Por, and Wood [emph{Discrete Comput. Geom.} 34(3):497--506, 2005].
قيم البحث
اقرأ أيضاً
We consider the number of distinct distances between two finite sets of points in ${bf R}^k$, for any constant dimension $kge 2$, where one set $P_1$ consists of $n$ points on a line $l$, and the other set $P_2$ consists of $m$ arbitrary points, such
that no hyperplane orthogonal to $l$ and no hypercylinder having $l$ as its axis contains more than $O(1)$ points of $P_2$. The number of distinct distances between $P_1$ and $P_2$ is then $$ Omegaleft(minleft{ n^{2/3}m^{2/3},; frac{n^{10/11}m^{4/11}}{log^{2/11}m},; n^2,; m^2right}right) . $$ Without the assumption on $P_2$, there exist sets $P_1$, $P_2$ as above, with only $O(m+n)$ distinct distances between them.
Given a finite point set $P$ in the plane, a subset $S subseteq P$ is called an island in $P$ if $conv(S) cap P = S$. We say that $Ssubset P$ is a visible island if the points in $S$ are pairwise visible and $S$ is an island in $P$. The famous Big-li
ne Big-clique Conjecture states that for any $k geq 3$ and $ell geq 4$, there is an integer $n = n(k,ell)$, such that every finite set of at least $n$ points in the plane contains $ell$ collinear points or $k$ pairwise visible points. In this paper, we show that this conjecture is false for visible islands, by constructing arbitrarily large finite point sets in the plane with no 4 collinear members and no visible island of size $2^{42}$.
We show that, for every set of $n$ points in the $d$-dimensional unit cube, there is an empty axis-parallel box of volume at least $Omega(d/n)$ as $ntoinfty$ and $d$ is fixed. In the opposite direction, we give a construction without an empty axis-pa
rallel box of volume $O(d^2log d/n)$. These improve on the previous best bounds of $Omega(log d/n)$ and $O(2^{7d}/n)$ respectively.
We study a combinatorial problem that recently arose in the context of shape optimization: among all triangles with vertices $(0,0)$, $(x,0)$, and $(0,y)$ and fixed area, which one encloses the most lattice points from $mathbb{Z}_{>0}^2$? Moreover, d
oes its shape necessarily converge to the isosceles triangle $(x=y)$ as the area becomes large? Laugesen and Liu suggested that, in contrast to similar problems, there might not be a limiting shape. We prove that the limiting set is indeed nontrivial and contains infinitely many elements. We also show that there exist `bad areas where no triangle is particularly good at capturing lattice points and show that there exists an infinite set of slopes $y/x$ such that any associated triangle captures more lattice points than any other fixed triangle for infinitely many (and arbitrarily large) areas; this set of slopes is a fractal subset of $[1/3, 3]$ and has Minkowski dimension at most $3/4$.
We say that a finite set of red and blue points in the plane in general position can be $K_{1,3}$-covered if the set can be partitioned into subsets of size $4$, with $3$ points of one color and $1$ point of the other color, in such a way that, if at
each subset the fourth point is connected by straight-line segments to the same-colored points, then the resulting set of all segments has no crossings. We consider the following problem: Given a set $R$ of $r$ red points and a set $B$ of $b$ blue points in the plane in general position, how many points of $Rcup B$ can be $K_{1,3}$-covered? and we prove the following results: (1) If $r=3g+h$ and $b=3h+g$, for some non-negative integers $g$ and $h$, then there are point sets $Rcup B$, like ${1,3}$-equitable sets (i.e., $r=3b$ or $b=3r$) and linearly separable sets, that can be $K_{1,3}$-covered. (2) If $r=3g+h$, $b=3h+g$ and the points in $Rcup B$ are in convex position, then at least $r+b-4$ points can be $K_{1,3}$-covered, and this bound is tight. (3) There are arbitrarily large point sets $Rcup B$ in general position, with $r=b+1$, such that at most $r+b-5$ points can be $K_{1,3}$-covered. (4) If $ble rle 3b$, then at least $frac{8}{9}(r+b-8)$ points of $Rcup B$ can be $K_{1,3}$-covered. For $r>3b$, there are too many red points and at least $r-3b$ of them will remain uncovered in any $K_{1,3}$-covering. Furthermore, in all the cases we provide efficient algorithms to compute the corresponding coverings.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
