A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets
The electronic journal of combinatorics, Tome 17 (2010)
Recently, Eisenbrand, Pach, Rothvoß, and Sopher studied the function $M(m, n)$, which is the largest cardinality of a convexly independent subset of the Minkowski sum of some planar point sets $P$ and $Q$ with $|P| = m$ and $|Q| = n$. They proved that $M(m,n)=O(m^{2/3}n^{2/3}+m+n)$, and asked whether a superlinear lower bound exists for $M(n,n)$. In this note, we show that their upper bound is the best possible apart from constant factors.
@article{10_37236_484,
author = {Ond\v{r}ej B{\'\i}lka and Kevin Buchin and Radoslav Fulek and Masashi Kiyomi and Yoshio Okamoto and Shin-ichi Tanigawa and Csaba D. T\'oth},
title = {A tight lower bound for convexly independent subsets of the {Minkowski} sums of planar point sets},
journal = {The electronic journal of combinatorics},
year = {2010},
volume = {17},
doi = {10.37236/484},
zbl = {1205.52010},
url = {http://geodesic.mathdoc.fr/articles/10.37236/484/}
}
TY - JOUR AU - Ondřej Bílka AU - Kevin Buchin AU - Radoslav Fulek AU - Masashi Kiyomi AU - Yoshio Okamoto AU - Shin-ichi Tanigawa AU - Csaba D. Tóth TI - A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets JO - The electronic journal of combinatorics PY - 2010 VL - 17 UR - http://geodesic.mathdoc.fr/articles/10.37236/484/ DO - 10.37236/484 ID - 10_37236_484 ER -
%0 Journal Article %A Ondřej Bílka %A Kevin Buchin %A Radoslav Fulek %A Masashi Kiyomi %A Yoshio Okamoto %A Shin-ichi Tanigawa %A Csaba D. Tóth %T A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets %J The electronic journal of combinatorics %D 2010 %V 17 %U http://geodesic.mathdoc.fr/articles/10.37236/484/ %R 10.37236/484 %F 10_37236_484
Ondřej Bílka; Kevin Buchin; Radoslav Fulek; Masashi Kiyomi; Yoshio Okamoto; Shin-ichi Tanigawa; Csaba D. Tóth. A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets. The electronic journal of combinatorics, Tome 17 (2010). doi: 10.37236/484
Cité par Sources :