Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEvery Large Point Set contains Many Collinear Points or an Empty Pentagon
239
0
0.0
(
0
)
Added by
David Wood
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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].
rate research
Read More
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-line 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-parallel 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, does 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
