Large convexly independent subsets of Minkowski sums

Details Large convexly independent subsets of Minkowski sums Large convexly independent subsets of Minkowski sums

2010-07-16

arxiv.org/abs/1007.2775v1

Electronic Journal of Combinatorics 17 (2010), #R146

Mathematics

Combinatorics

7 pages

Scientific paper

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)\geq \Omega(n\sqrt{\log n})$, which answers a question of Eisenbrand, Pach, Rothvo\ss, 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 $\lfloor\frac{1}{3}n^2\rfloor\leq E_3(n)\leq \frac{3}{8}n^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 $d\geq 3$ that $W_d(n)\sim\frac12\left(1-\frac{1}{a(d)}\right)n^2$, where $a(d)\in N$ 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.

Affiliated with

Also associated with

No associations

Rating

Large convexly independent subsets of Minkowski sums does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large convexly independent subsets of Minkowski sums, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large convexly independent subsets of Minkowski sums will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-51123