اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدExact generating function for 2-convex polygons
663
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Polygons are described as almost-convex if their perimeter differs from the perimeter of their minimum bounding rectangle by twice their `concavity index, $m$. Such polygons are called emph{$m$-convex} polygons and are characterised by having up to $m$ indentations in their perimeter. We first describe how we conjectured the (isotropic) generating function for the case $m=2$ using a numerical procedure based on series expansions. We then proceed to prove this result for the more general case of the full anisotropic generating function, in which steps in the $x$ and $y$ direction are distinguished. In so doing, we develop tools that would allow for the case $m > 2$ to be studied. %In our proof we use a `divide and conquer approach, factorising 2-convex %polygons by extending a line along the base of its indents. We then use %the inclusion-exclusion principle, the Hadamard product and extensions to %known methods to derive the generating functions for each case.
قيم البحث
اقرأ أيضاً
Polygons are described as almost-convex if their perimeter differs from the perimeter of their minimum bounding rectangle by twice their `concavity index, $m$. Such polygons are called emph{$m$-convex} polygons and are characterised by having up to $
m$ indentations in the side. We use a `divide and conquer approach, factorising 2-convex polygons by extending a line along the base of its indents. We then use the inclusion-exclusion principle, the Hadamard product and extensions to known methods to derive the generating functions for each case.
We characterize the topological configurations of points and lines that may arise when placing n points on a circle and drawing the n perpendicular bisectors of the sides of the corresponding convex cyclic n-gon. We also provide exact and asymptotic
formulas describing a random realizable configuration, obtained either by sampling the points uniformly at random on the circle or by sampling a realizable configuration uniformly at random.
Let $S$ be a set of $n$ points in general position in the plane, and let $X_{k,ell}(S)$ be the number of convex $k$-gons with vertices in $S$ that have exactly $ell$ points of $S$ in their interior. We prove several equalities for the numbers $X_{k,e
ll}(S)$. This problem is related to the ErdH{o}s-Szekeres theorem. Some of the obtained equations also extend known equations for the numbers of empty convex polygons to polygons with interior points. Analogous results for higher dimension are shown as well.
We study several problems concerning convex polygons whose vertices lie in a Cartesian product (for short, grid) of two sets of n real numbers. First, we prove that every such grid contains a convex polygon with $Omega$(log n) vertices and that this
bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d $in$ N), and obtain a tight lower bound of $Omega$(log d--1 n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the largest convex chain in a grid that contains no two points of the same x-or y-coordinate. We show how to efficiently approximate the maximum size of a supported convex polygon up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
The generating function and an explicit expression is derived for the (colored) Motzkin numbers of higher rank introduced recently. Considering the special case of rank one yields the corresponding results for the conventional colored Motzkin numbers
for which in addition a recursion relation is given.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
