A Tight Lower Bound for Convexly Independent Subsets of the Minkowski Sums of Planar Point Sets
Ondřej Bílka, Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Shin‐ichi Tanigawa, Csaba D. Tóth · The Electronic Journal of Combinatorics · 2010
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2010
Abstract
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.
Open the resolved locator · 10.37236/484
Metadata licence: OpenAlex metadata (CC0)