A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets

MaRDI QIDQ612909zbMATH OpenFDO

Authors Ondřej Bílka, Kevin Buchin, Radoslav Fulek, Masashi Kiyomi, Yoshio Okamoto, Csaba D. Tóth, Shin-Ichi Tanigawa

Publication date 16 December 2010

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

Full work available at URL https://eudml.org/doc/228690, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1n35.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) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Review text

Summary: Recently, \textit{F. Eisenbrand, J. Pach, Th. Rothvoß} and \textit{N. B. Sopher} [Electron. J. Comb. 15, No.~1, Research Paper N8, 4~p. (2008; Zbl 1160.52013)] studied the function \(M (m, n)\), which is the largest cardinality of a convexly independent subset of the Minkowski sum of some planar point sets \(P\) and \(Q\) with \(|P| = m\) and \(|Q| = n\). They proved that \(M (m, n) = O(m^{2/3}n^{2/3} + m + n)\), and asked whether a superlinear lower bound exists for \(M (n, n)\). In this note, we show that their upper bound is the best possible apart from constant factors.

Recommendations

• Convexly independent subsets of the Minkowski sum of planar point sets
• Convexly independent subsets of Minkowski sums of convex polygons
• On the largest convex subsets in Minkowski sums
• Large convexly independent subsets of Minkowski sums

Cited in

(11)

• Convexly independent subsets of the Minkowski sum of planar point sets
• Convexly independent subsets of Minkowski sums of convex polygons
• The convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flores theorem
• A \(\tau \)-conjecture for Newton polygons
• Minkowski complexes and convex threshold dimension
• On the largest convex subsets in Minkowski sums
• Drawing graphs with vertices and edges in convex position
• Minkowski Sum Selection and Finding
• Minkowski complexity of sets: an easy lower bound
• Constrained independence system and triangulations of planar point sets
• Large convexly independent subsets of Minkowski sums

This page was built for publication: A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets

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