Convexly independent subsets of the Minkowski sum of planar point sets
Eisenbrand, Friedrich; Pach, János; Rothvoß, Thomas; Sopher, Nir B.
2008

Files

Abstract

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)).

Details

Title Convexly independent subsets of the Minkowski sum of planar point sets
Author(s) Eisenbrand, Friedrich ; Pach, János ; Rothvoß, Thomas ; Sopher, Nir B.
Published in Electronic Journal of Combinatorics
Volume 15
Issue 1
Pages Note 8, 4
Date 2008
Publisher American Mathematical Society
ISSN 1077-8926
Keywords
Note Professor Pach's number: [224]
Other identifier(s) View record in Web of Science
DAR: 11834
Additional link URL
Laboratories DISOPT
DCG
Record Appears in Scientific production and competences > SB - School of Basic Sciences > MATH - Institute of Mathematics > DISOPT - Chair of Discrete Optimization
Scientific production and competences > SB - School of Basic Sciences > SB Archives > DCG - Chair of Combinatorial Geometry
Scientific production and competences > SB - School of Basic Sciences > Mathematics
Peer-reviewed publications
Work produced at EPFL
Journal Articles
Published
Record creation date 2008-08-21

PDF