tailieunhanh - Báo cáo toán học: "A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài:A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets. | A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets Ondrej BilkaJ Kevin Buclme Radoslav Fulek Masashi Kiyomi Yoshio Okamoto Shin-ichi Tanigawa Csaba D. Tóthb Submitted Jul 31 2009 Accepted Oct 13 2010 Published Oct 29 2010 Mathematics Subject Classification 52C35 52A10 Abstract Recently Eisenbrand Pach Rothvofi and Sopher 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 m2 3n2 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. 1 Introduction Recently Eisenbrand Pach Rothvob and Sopher 1 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 Preliminary versions of our results have been presented at the Czech-Slovakian Student Competition in Mathematics and Computer Science Kosice May 27-29 2009 and at the 7th Japan Conference on Computational Geometry and Graphs Kanazawa November 11-13 2009 . A part of the work has been done at the 12th Korean Workshop on Computational Geometry June 2009 and at the 7th Gremo Workshop on Open Problems July 2009. The authors thank the organizers of these workshops. 1 Charles University. Email ondra@. Technische Universiteit Eindhoven. Email . Supported by the Netherlands Organisation for Scientific Research NWO under project no. . Ecole Polytechnique Federale de Lausanne. Email . Partially supported by Discrete and Convex Geometry project MTKD-CT-2005-014333 of the European Community. Japan Advanced Institute of Science and Technology. Email mkiyomi@. Tokyo Institute of Technology. Email okamoto@. Supported by Global COE