Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExact generating function for 2-convex polygons
643
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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,ell}(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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
