Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn weighted sums of numbers of convex polygons in point sets
204
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Given a finite set $A subseteq mathbb{R}^d$, points $a_1,a_2,dotsc,a_{ell} in A$ form an $ell$-hole in $A$ if they are the vertices of a convex polytope which contains no points of $A$ in its interior. We construct arbitrarily large point sets in general position in $mathbb{R}^d$ having no holes of size $O(4^ddlog d)$ or more. This improves the previously known upper bound of order $d^{d+o(d)}$ due to Valtr. The basic version of our construction uses a certain type of equidistributed point sets, originating from numerical analysis, known as $(t,m,s)$-nets or $(t,s)$-sequences, yielding a bound of $2^{7d}$. The better bound is obtained using a variant of $(t,m,s)$-nets, obeying a relaxed equidistribution condition.
For a real number $t$, let $r_ell(t)$ be the total weight of all $t$-large Schr{o}der paths of length $ell$, and $s_ell(t)$ be the total weight of all $t$-small Schr{o}der paths of length $ell$. For constants $alpha, beta$, in this article we derive recurrence formulae for the determinats of the Hankel matrices $det_{1le i,jle n} (alpha r_{i+j-2}(t) +beta r_{i+j-1}(t))$, $det_{1le i,jle n} (alpha r_{i+j-1}(t) +beta r_{i+j}(t))$, $det_{1le i,jle n} (alpha s_{i+j-2}(t) +beta s_{i+j-1}(t))$, and $det_{1le i,jle n} (alpha s_{i+j-1}(t) +beta s_{i+j}(t))$ combinatorially via suitable lattice path models.
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.
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.
Given a colored point set in the plane, a perfect rainbow polygon is a simple polygon that contains exactly one point of each color, either in its interior or on its boundary. Let $operatorname{rb-index}(S)$ denote the smallest size of a perfect rainbow polygon for a colored point set $S$, and let $operatorname{rb-index}(k)$ be the maximum of $operatorname{rb-index}(S)$ over all $k$-colored point sets in general position; that is, every $k$-colored point set $S$ has a perfect rainbow polygon with at most $operatorname{rb-index}(k)$ vertices. In this paper, we determine the values of $operatorname{rb-index}(k)$ up to $k=7$, which is the first case where $operatorname{rb-index}(k) eq k$, and we prove that for $kge 5$, [ frac{40lfloor (k-1)/2 rfloor -8}{19} %Birgit: leqoperatorname{rb-index}(k)leq 10 bigglfloorfrac{k}{7}biggrfloor + 11. ] Furthermore, for a $k$-colored set of $n$ points in the plane in general position, a perfect rainbow polygon with at most $10 lfloorfrac{k}{7}rfloor + 11$ vertices can be computed in $O(nlog n)$ time.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
