Convexly independent subsets of the Minkowski sum of planar point sets

• Published in: Electronic Journal of Combinatorics (ISSN: 1077-8926), vol. 15, num. 1, p. Note 8, 4
• American Mathematical Society, 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 ⊆ P⊕Q which consist of convex independent points. We show that, if P and Q contain at most n points, then |S| = O(n^(4/3)).

Note: Professor Pach's number: [224]

Keywords: Minkowski sum ; planar point sets

Reference

• DISOPT-ARTICLE-2008-001
• doi:NA
• View record in Web of Science

• URL: http://cs.anu.edu.au/publications/eljc/Volume_15/v15i1toc.html

Record created on 2008-08-21, modified on 2012-03-28