Geodesic
A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets
The electronic journal of combinatorics, Tome 17 (2010)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
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.
DOI : 10.37236/484
Classification : 52C10, 52C35, 52A10 
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
@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

Cité par Sources :