ترغب بنشر مسار تعليمي؟ اضغط هنا

The layer number of $alpha$-evenly distributed point sets

56   0   0.0 ( 0 )
 نشر من قبل Minki Kim
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

For a finite point set in $mathbb{R}^d$, we consider a peeling process where the vertices of the convex hull are removed at each step. The layer number $L(X)$ of a given point set $X$ is defined as the number of steps of the peeling process in order to delete all points in $X$. It is known that if $X$ is a set of random points in $mathbb{R}^d$, then the expectation of $L(X)$ is $Theta(|X|^{2/(d+1)})$, and recently it was shown that if $X$ is a point set of the square grid on the plane, then $L(X)=Theta(|X|^{2/3})$. In this paper, we investigate the layer number of $alpha$-evenly distributed point sets for $alpha>1$; these point sets share the regularity aspect of random point sets but in a more general setting. The set of lattice points is also an $alpha$-evenly distributed point set for some $alpha>1$. We find an upper bound of $O(|X|^{3/4})$ for the layer number of an $alpha$-evenly distributed point set $X$ in a unit disk on the plane for some $alpha>1$, and provide an explicit construction that shows the growth rate of this upper bound cannot be improved. In addition, we give an upper bound of $O(|X|^{frac{d+1}{2d}})$ for the layer number of an $alpha$-evenly distributed point set $X$ in a unit ball in $mathbb{R}^d$ for some $alpha>1$ and $dgeq 3$.



قيم البحث

اقرأ أيضاً

Evenly convex sets in a topological vector space are defined as the intersection of a family of open half spaces. We introduce a generalization of this concept in the conditional framework and provide a generalized version of the bipolar theorem. Thi s notion is then applied to obtain the dual representation of conditionally evenly quasi-convex maps.
We count the ordered sum-free triplets of subsets in the group $mathbb{Z}/pmathbb{Z}$, i.e., the triplets $(A,B,C)$ of sets $A,B,C subset mathbb{Z}/pmathbb{Z}$ for which the equation $a+b=c$ has no solution with $ain A$, $b in B$ and $c in C$. Our ma in theorem improves on a recent result by Semchankau, Shabanov, and Shkredov using a different and simpler method. Our proof relates previous results on the number of independent sets of regular graphs by Kahn, Perarnau and Perkins, and Csikvari to produce explicit estimates on smaller order terms. We also obtain estimates for the number of sum-free triplets of subsets in a general abelian group.
This paper studies problems related to visibility among points in the plane. A point $x$ emph{blocks} two points $v$ and $w$ if $x$ is in the interior of the line segment $bar{vw}$. A set of points $P$ is emph{$k$-blocked} if each point in $P$ is ass igned one of $k$ colours, such that distinct points $v,win P$ are assigned the same colour if and only if some other point in $P$ blocks $v$ and $w$. The focus of this paper is the conjecture that each $k$-blocked set has bounded size (as a function of $k$). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterise all sets ${n_1,n_2,n_3,n_4}$ such that some 4-blocked set has exactly $n_i$ points in the $i$-th colour class. Amongst other results, for infinitely many values of $k$, we construct $k$-blocked sets with $k^{1.79...}$ points.
A subset of vertices is a {it maximum independent set} if no two of the vertices are adjacent and the subset has maximum cardinality. A subset of vertices is called a {it maximum dissociation set} if it induces a subgraph with vertex degree at most 1 , and the subset has maximum cardinality. Zito [J. Graph Theory {bf 15} (1991) 207--221] proved that the maximum number of maximum independent sets of a tree of order $n$ is $2^{frac{n-3}{2}}$ if $n$ is odd, and $2^{frac{n-2}{2}}+1$ if $n$ is even and also characterized all extremal trees with the most maximum independent sets, which solved a question posed by Wilf. Inspired by the results of Zito, in this paper, by establishing four structure theorems and a result of $k$-K{o}nig-Egerv{a}ry graph, we show that the maximum number of maximum dissociation sets in a tree of order $n$ is begin{center} $left{ begin{array}{ll} 3^{frac{n}{3}-1}+frac{n}{3}+1, & hbox{if $nequiv0pmod{3}$;} 3^{frac{n-1}{3}-1}+1, & hbox{if $nequiv1pmod{3}$;} 3^{frac{n-2}{3}-1}, & hbox{if $nequiv2pmod{3}$,} end{array} right.$ end{center} and also give complete structural descriptions of all extremal trees on which these maxima are achieved.
Let $T$ be a rooted tree, and $V(T)$ its set of vertices. A subset $X$ of $V(T)$ is called an infima closed set of $T$ if for any two vertices $u,vin X$, the first common ancestor of $u$ and $v$ is also in $X$. This paper determines the trees with mi nimum number of infima closed sets among all rooted trees of given order, thereby answering a question of Klazar. It is shown that these trees are essentially complete binary trees, with the exception of vertices at the last levels. Moreover, an asymptotic estimate for the minimum number of infima closed sets in a tree with $n$ vertices is also provided.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا