Large convexly independent subsets of Minkowski sums

MaRDI QIDQ612927zbMATH OpenFDO

Authors Konrad J. Swanepoel, Pavel Valtr

Publication date 16 December 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.2775, https://eudml.org/doc/232452, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r146.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: Let $E_d(n)$ be the maximum number of pairs that can be selected from a set of $n$ points in $R^d$ such that the midpoints of these pairs are convexly independent. We show that $E_2(n)geqOmega(nsqrtlogn)$, which answers a question of Eisenbrand, Pach, Rothvoss, and Sopher (2008) on large convexly independent subsets in Minkowski sums of finite planar sets, as well as a question of Halman, Onn, and Rothblum (2007). We also show that $lfloorfrac13n^{2}floorleq{E}_3(n)leqfrac38n^2+O(n^{3/2})$. Let $W_d(n)$ be the maximum number of pairwise nonparallel unit distance pairs in a set of $n$ points in some $d$-dimensional strictly convex normed space. We show that $W_2(n)=Theta(E_2(n))$ and for $dgeq3$ that $W_d(n)simfrac12left(1-frac1a(d)ight)n^2$, where $a(d)inN$ is related to strictly antipodal families. In fact we show that the same asymptotics hold without the requirement that the unit distance pairs form pairwise nonparallel segments, and also if diameter pairs are considered instead of unit distance pairs.

Recommendations

• Convexly independent subsets of the Minkowski sum of planar point sets
• A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets
• On the largest convex subsets in Minkowski sums
• Convexly independent subsets of Minkowski sums of convex polygons
• The number of extreme pairs of finite point-sets in Euclidean spaces

Cited in

(9)

• On the largest convex subsets in Minkowski sums
• scientific article; zbMATH DE number 2058507 (Why is no real title available?)
• A \(\tau \)-conjecture for Newton polygons
• Convexly independent subsets of Minkowski sums of convex polygons
• The convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flores theorem
• Drawing graphs with vertices and edges in convex position
• Absolutely convex sets of large Szlenk index
• A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets
• Convexly independent subsets of the Minkowski sum of planar point sets

This page was built for publication: Large convexly independent subsets of Minkowski sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q612927)