Convexly independent subsets of the Minkowski sum of planar point sets
The electronic journal of combinatorics, Tome 15 (2008)
Let $P$ and $Q$ be finite sets of points in the plane. In this note we consider the largest cardinality of a subset of the Minkowski sum $S\subseteq P \oplus Q$ which consist of convexly independent points. We show that, if $|P| = m$ and $|Q| = n$ then $|S| = O(m^{2/3} n^{2/3} + m + n)$.
@article{10_37236_883,
author = {Friedrich Eisenbrand and J\'anos Pach and Thomas Rothvo{\ss} and Nir B. Sopher},
title = {Convexly independent subsets of the {Minkowski} sum of planar point sets},
journal = {The electronic journal of combinatorics},
year = {2008},
volume = {15},
doi = {10.37236/883},
zbl = {1160.52013},
url = {http://geodesic.mathdoc.fr/articles/10.37236/883/}
}
TY - JOUR AU - Friedrich Eisenbrand AU - János Pach AU - Thomas Rothvoß AU - Nir B. Sopher TI - Convexly independent subsets of the Minkowski sum of planar point sets JO - The electronic journal of combinatorics PY - 2008 VL - 15 UR - http://geodesic.mathdoc.fr/articles/10.37236/883/ DO - 10.37236/883 ID - 10_37236_883 ER -
%0 Journal Article %A Friedrich Eisenbrand %A János Pach %A Thomas Rothvoß %A Nir B. Sopher %T Convexly independent subsets of the Minkowski sum of planar point sets %J The electronic journal of combinatorics %D 2008 %V 15 %U http://geodesic.mathdoc.fr/articles/10.37236/883/ %R 10.37236/883 %F 10_37236_883
Friedrich Eisenbrand; János Pach; Thomas Rothvoß; Nir B. Sopher. Convexly independent subsets of the Minkowski sum of planar point sets. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/883
Cité par Sources :