go-v.orgdoi

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

  • DOI 10.37236/484
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 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)